×

zbMATH — the first resource for mathematics

General theoretical results on rectilinear embeddability of graphs. (English) Zbl 0732.05021
Summary: In the design of certain kinds of electronic circuits the following question arises: given a non-negative integer k, what graphs admit of a plane embedding such that every edge is a broken line formed by horizontal and vertical segments and having at most k bends? Any such graph is said to be k-rectilinear. No matter what k is, an obvious necessary condition for k-rectilinearity is that the degree of each vertex does not exceed four.
Our main result is that every planar graph H satisfying this condition is 3-rectilinear: in fact, it is 2-rectilinear with the only exception of the octahedron. We also outline a polynomial-time algorithm which actually constructs a plane embedding of H with at most 2 bends (3 bends if H is the octahedron) on each edge. The resulting embedding has the property that the total number of bends does not exceed 2n, where n is the number of vertices of H.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
94C15 Applications of graph theory to circuits and networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Y. Liu, Boolean approach to planar embeddings of a graph,Acta Math. Sinica, New Series,5 (1989), 44–79. · Zbl 0780.05017
[2] R. Tamassia and I. G. Tollis, A Provably Good Linear Algorithm for Embedding Graphs in the Rectilinear Grid, UILU-ENG-85-2233, ACT-64, Coordinated Science Laboratory, Uni. Illinois, 1985.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.