At most single-bend embeddings of cubic graphs

DOI10.1007/BF02662066MaRDI QIDQ1335404zbMATH OpenOpenAlexFDO

Authors Yanpei Liu, Paola Marchioro, Rossella Petreschi

Publication date 7 March 1995

Published in Applied Mathematics. Series B (English Edition) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02662066

zbMATH Keywords

bendcubic graphplanesingle-bend embeddingsVLSI design

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15) Applications of graph theory to circuits and networks (94C15)

Review text

A graph is said to be single-bend embeddable if it has an embedding in the plane for which every edge consists of at most two horizontal or vertical line segments. (A bend is the intersection point of two line segments, one horizontal and the other vertical, whose union represents one edge.) It is shown that every cubic connected planar graph except \(K_ 4\) is single-bend embeddable. An \(O(n)\) amortized time algorithm is given for drawing a single-bend embeddable cubic graph of order \(n\). It is shown that the minimum total number of bends for a single-bend embeddable cubic graph of order \(n\) is at most \(n/2 + 1\); the result is best possible. This study has relevance to VLSI design.

Recommendations

• General theoretical results on rectilinear embeddability of graphs
• Theoretical results on at most 1-bend embeddability of graphs
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• scientific article; zbMATH DE number 2080108

Cites work

• Algorithms for drawing graphs: An annotated bibliography
• Computing an st-numbering
• General theoretical results on rectilinear embeddability of graphs
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3241107 (Why is no real title available?)
• scientific article; zbMATH DE number 3315017 (Why is no real title available?)
• Planar graphs: Theory and algorithms
• Theoretical results on at most 1-bend embeddability of graphs

Cited in

(8)

• Theoretical results on at most 1-bend embeddability of graphs
• Some combinatorial optimization problems arising from VLSI circuit design
• Boolean approaches to graph embeddings related to VLSI
• Drawing planar graphs using the canonical ordering
• Orthogonal drawings of graphs for the automation of VLSI circuit design
• Grid straight-line embeddings of trees with a minimum number of bends per path
• Variants of the segment number of a graph
• An efficient orthogonal grid drawing algorithm for cubic graphs

This page was built for publication: At most single-bend embeddings of cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1335404)