Planar grid embedding in linear time

The authors consider the problem of constructing a planar grid embedding for G, where G is a planar graph with n vertices, which maps vertices to distinct grid points and edges to nonintersecting grid paths. A new algorithm is presented that runs in O(n) time and produces grid embeddings with the fo...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on circuits and systems 1989-09, Vol.36 (9), p.1230-1234
Main Authors: Tamassia, R., Tollis, I.G.
Format: Article
Language:English
Subjects:
Chaos
Circuit analysis
Circuit theory
Combinatorics
Combinatorics. Ordered structures
Differential equations
Eigenvalues and eigenfunctions
Exact sciences and technology
Graph theory
Graphics
Jacobian matrices
Mathematics
Nonlinear systems
Piecewise linear techniques
Sciences and techniques of general use
Vectors
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c273t-f269de11e7cf22b991f3630162063e95d7cf41a451c5a91fdacfac0a5b6da5b43
cites cdi_FETCH-LOGICAL-c273t-f269de11e7cf22b991f3630162063e95d7cf41a451c5a91fdacfac0a5b6da5b43
container_end_page 1234
container_issue 9
container_start_page 1230
container_title IEEE transactions on circuits and systems
container_volume 36
creator Tamassia, R.
Tollis, I.G.
description The authors consider the problem of constructing a planar grid embedding for G, where G is a planar graph with n vertices, which maps vertices to distinct grid points and edges to nonintersecting grid paths. A new algorithm is presented that runs in O(n) time and produces grid embeddings with the following properties: (1) the total number of bends is at most 2.4n+2; (2) the number of bends along each edge is at most 4; (3) the length of every edge is O(n); and (4) the area of the embedding is O(n/sup 2/).< >
doi_str_mv 10.1109/31.34669
format article
fullrecord <record><control><sourceid>pascalfrancis_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1109_31_34669</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>34669</ieee_id><sourcerecordid>19778390</sourcerecordid><originalsourceid>FETCH-LOGICAL-c273t-f269de11e7cf22b991f3630162063e95d7cf41a451c5a91fdacfac0a5b6da5b43</originalsourceid><addsrcrecordid>eNpFjztLxEAUhQdRcF0FW7sUCjZZ751XZkpZfMGCFlqHm3ksI0lcZrbx3xuNaHMP3O_jwGHsHGGFCPZG4EpIre0BW6BSpkbe6EO2ALCmlmDlMTsp5R0AjDVmwS5fehopV9ucfBWGLnifxm2VxqpPY5jAPg3hlB1F6ks4-80le7u_e10_1pvnh6f17aZ2vBH7OnJtfUAMjYucd9ZiFFoAag5aBKv89JdIUqFTNEFPLpIDUp3205Fiya7nXpc_SskhtrucBsqfLUL7va4V2P6sm9SrWd1RcdTHTKNL5d-3TWOEhcm7mL0UQvjDc8cXIrhVVw</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Planar grid embedding in linear time</title><source>IEEE Xplore (Online service)</source><creator>Tamassia, R. ; Tollis, I.G.</creator><creatorcontrib>Tamassia, R. ; Tollis, I.G.</creatorcontrib><description>The authors consider the problem of constructing a planar grid embedding for G, where G is a planar graph with n vertices, which maps vertices to distinct grid points and edges to nonintersecting grid paths. A new algorithm is presented that runs in O(n) time and produces grid embeddings with the following properties: (1) the total number of bends is at most 2.4n+2; (2) the number of bends along each edge is at most 4; (3) the length of every edge is O(n); and (4) the area of the embedding is O(n/sup 2/).&lt; &gt;</description><identifier>ISSN: 0098-4094</identifier><identifier>EISSN: 1558-1276</identifier><identifier>DOI: 10.1109/31.34669</identifier><identifier>CODEN: ICSYBT</identifier><language>eng</language><publisher>New York, NY: IEEE</publisher><subject>Chaos ; Circuit analysis ; Circuit theory ; Combinatorics ; Combinatorics. Ordered structures ; Differential equations ; Eigenvalues and eigenfunctions ; Exact sciences and technology ; Graph theory ; Graphics ; Jacobian matrices ; Mathematics ; Nonlinear systems ; Piecewise linear techniques ; Sciences and techniques of general use ; Vectors</subject><ispartof>IEEE transactions on circuits and systems, 1989-09, Vol.36 (9), p.1230-1234</ispartof><rights>1991 INIST-CNRS</rights><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c273t-f269de11e7cf22b991f3630162063e95d7cf41a451c5a91fdacfac0a5b6da5b43</citedby><cites>FETCH-LOGICAL-c273t-f269de11e7cf22b991f3630162063e95d7cf41a451c5a91fdacfac0a5b6da5b43</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/34669$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>314,777,781,27905,27906,54777</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=19778390$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Tamassia, R.</creatorcontrib><creatorcontrib>Tollis, I.G.</creatorcontrib><title>Planar grid embedding in linear time</title><title>IEEE transactions on circuits and systems</title><addtitle>T-CAS</addtitle><description>The authors consider the problem of constructing a planar grid embedding for G, where G is a planar graph with n vertices, which maps vertices to distinct grid points and edges to nonintersecting grid paths. A new algorithm is presented that runs in O(n) time and produces grid embeddings with the following properties: (1) the total number of bends is at most 2.4n+2; (2) the number of bends along each edge is at most 4; (3) the length of every edge is O(n); and (4) the area of the embedding is O(n/sup 2/).&lt; &gt;</description><subject>Chaos</subject><subject>Circuit analysis</subject><subject>Circuit theory</subject><subject>Combinatorics</subject><subject>Combinatorics. Ordered structures</subject><subject>Differential equations</subject><subject>Eigenvalues and eigenfunctions</subject><subject>Exact sciences and technology</subject><subject>Graph theory</subject><subject>Graphics</subject><subject>Jacobian matrices</subject><subject>Mathematics</subject><subject>Nonlinear systems</subject><subject>Piecewise linear techniques</subject><subject>Sciences and techniques of general use</subject><subject>Vectors</subject><issn>0098-4094</issn><issn>1558-1276</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1989</creationdate><recordtype>article</recordtype><recordid>eNpFjztLxEAUhQdRcF0FW7sUCjZZ751XZkpZfMGCFlqHm3ksI0lcZrbx3xuNaHMP3O_jwGHsHGGFCPZG4EpIre0BW6BSpkbe6EO2ALCmlmDlMTsp5R0AjDVmwS5fehopV9ucfBWGLnifxm2VxqpPY5jAPg3hlB1F6ks4-80le7u_e10_1pvnh6f17aZ2vBH7OnJtfUAMjYucd9ZiFFoAag5aBKv89JdIUqFTNEFPLpIDUp3205Fiya7nXpc_SskhtrucBsqfLUL7va4V2P6sm9SrWd1RcdTHTKNL5d-3TWOEhcm7mL0UQvjDc8cXIrhVVw</recordid><startdate>19890901</startdate><enddate>19890901</enddate><creator>Tamassia, R.</creator><creator>Tollis, I.G.</creator><general>IEEE</general><general>Institute of Electrical and Electronics Engineers</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>19890901</creationdate><title>Planar grid embedding in linear time</title><author>Tamassia, R. ; Tollis, I.G.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c273t-f269de11e7cf22b991f3630162063e95d7cf41a451c5a91fdacfac0a5b6da5b43</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1989</creationdate><topic>Chaos</topic><topic>Circuit analysis</topic><topic>Circuit theory</topic><topic>Combinatorics</topic><topic>Combinatorics. Ordered structures</topic><topic>Differential equations</topic><topic>Eigenvalues and eigenfunctions</topic><topic>Exact sciences and technology</topic><topic>Graph theory</topic><topic>Graphics</topic><topic>Jacobian matrices</topic><topic>Mathematics</topic><topic>Nonlinear systems</topic><topic>Piecewise linear techniques</topic><topic>Sciences and techniques of general use</topic><topic>Vectors</topic><toplevel>online_resources</toplevel><creatorcontrib>Tamassia, R.</creatorcontrib><creatorcontrib>Tollis, I.G.</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><jtitle>IEEE transactions on circuits and systems</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Tamassia, R.</au><au>Tollis, I.G.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Planar grid embedding in linear time</atitle><jtitle>IEEE transactions on circuits and systems</jtitle><stitle>T-CAS</stitle><date>1989-09-01</date><risdate>1989</risdate><volume>36</volume><issue>9</issue><spage>1230</spage><epage>1234</epage><pages>1230-1234</pages><issn>0098-4094</issn><eissn>1558-1276</eissn><coden>ICSYBT</coden><abstract>The authors consider the problem of constructing a planar grid embedding for G, where G is a planar graph with n vertices, which maps vertices to distinct grid points and edges to nonintersecting grid paths. A new algorithm is presented that runs in O(n) time and produces grid embeddings with the following properties: (1) the total number of bends is at most 2.4n+2; (2) the number of bends along each edge is at most 4; (3) the length of every edge is O(n); and (4) the area of the embedding is O(n/sup 2/).&lt; &gt;</abstract><cop>New York, NY</cop><pub>IEEE</pub><doi>10.1109/31.34669</doi><tpages>5</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0098-4094
ispartof IEEE transactions on circuits and systems, 1989-09, Vol.36 (9), p.1230-1234
issn 0098-4094
1558-1276
language eng
recordid cdi_crossref_primary_10_1109_31_34669
source IEEE Xplore (Online service)
subjects Chaos
Circuit analysis
Circuit theory
Combinatorics
Combinatorics. Ordered structures
Differential equations
Eigenvalues and eigenfunctions
Exact sciences and technology
Graph theory
Graphics
Jacobian matrices
Mathematics
Nonlinear systems
Piecewise linear techniques
Sciences and techniques of general use
Vectors
title Planar grid embedding in linear time
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-19T08%3A58%3A45IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-pascalfrancis_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Planar%20grid%20embedding%20in%20linear%20time&rft.jtitle=IEEE%20transactions%20on%20circuits%20and%20systems&rft.au=Tamassia,%20R.&rft.date=1989-09-01&rft.volume=36&rft.issue=9&rft.spage=1230&rft.epage=1234&rft.pages=1230-1234&rft.issn=0098-4094&rft.eissn=1558-1276&rft.coden=ICSYBT&rft_id=info:doi/10.1109/31.34669&rft_dat=%3Cpascalfrancis_cross%3E19778390%3C/pascalfrancis_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c273t-f269de11e7cf22b991f3630162063e95d7cf41a451c5a91fdacfac0a5b6da5b43%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=34669&rfr_iscdi=true