Embedding rectilinear graphs in linear time

DOI10.1016/0020-0190(88)90032-4MaRDI QIDQ1111399zbMATH OpenOpenAlexFDO

Authors Frank Hoffmann, Klaus Kriegel

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(88)90032-4

zbMATH Keywords

graph embeddinglinear-time algorithmrectilinear graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (including graph drawing) in computer science (68R10)

Review text

A linear-time algorithm is presented to recognize and embed rectilinear graphs which are embeddable on the plane. Previously, only the \(O(n^ 2)\) time algorithm of \textit{G. Vijayan} and \textit{A. Wigderson} [SIAM J. Comput. 14, 355-372 (1985; Zbl 0568.05024)] was known. The algorithm described here uses a different and surprisingly simple strategy.

Recommendations

• Rectilinear Graphs and Their Embeddings
• General theoretical results on rectilinear embeddability of graphs
• A linear-time algorithm for drawing a planar graph on a grid
• A linear-time algorithm for drawing a planar graph on an (n-2) (n-2) grid.
• Planar rectilinear drawings of outerplanar graphs in linear time

Cites work

• Automata and Labyrinths
• scientific article; zbMATH DE number 3827906 (Why is no real title available?)
• scientific article; zbMATH DE number 3722098 (Why is no real title available?)
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Rectilinear Graphs and Their Embeddings
• The embeddings of a graph—A survey

Cited in

(9)

• Representations of graphs and networks (coding, layouts and embeddings)
• HV-planarity: algorithms and complexity
• Linear time construction of indexable elastic founder graphs
• Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
• Connected Rectilinear Graphs on Point Sets
• Rectilinear Graphs and Their Embeddings
• Level Planar Embedding in Linear Time
• scientific article; zbMATH DE number 1839533 (Why is no real title available?)
• On the complexity of orthogonal compaction

This page was built for publication: Embedding rectilinear graphs in linear time

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