A new algorithm for embedding plane graphs at fixed vertex locations

DOI10.37236/10106MaRDI QIDQ2121749zbMATH OpenOpenAlexFDO

Authors Marcus Schaefer

Publication date 4 April 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/10106

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

fixed-vertex locationgraph embeddingplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

This paper studies the problem of embedding a plane graph at pre-assigned fixed vertex locations with at most \(2.5n+1\) bends allowed per edge where \(n\) is the number of vertices of the graph. The complexity of the drawing is measured by the number of bends, two straight lines are joined at bends and a single straight line is 0-bend. The proposed algorithm improves the result by \textit{J. Pach} and \textit{R. Wenger} [Graphs Comb. 17, No. 4, 717--728 (2001; Zbl 0991.05036)], where the upper bound on the number of bends was \(24(n+2)\). Moreover, the proposed algorithm is extended to grid embeddings, orthogonal embeddings, and min-length embeddings. The time complexity of the proposed approach is quadratic.

Recommendations

• Embedding planar graphs at fixed vertex locations
• scientific article; zbMATH DE number 1500681
• Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
• Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations
• An algorithm for 1-bend embeddings of plane graphs in the two-dimensional grid

Cites work

• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• A theorem on graphs
• Arboricity and Subgraph Listing Algorithms
• Automatische Abbildung eines planaren Graphen in die Ebene mit beliebig vorgebbaren Örtern der Knotenbilder
• Drawing colored graphs on colored points
• Drawing partially embedded and simultaneously planar graphs
• Embedding planar graphs at fixed vertex locations
• Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
• Extending Partial Orthogonal Drawings
• scientific article; zbMATH DE number 3882232 (Why is no real title available?)
• scientific article; zbMATH DE number 3523640 (Why is no real title available?)
• Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations
• Simultaneous embeddings with vertices mapping to pre-specified points
• Triangulating planar graphs while minimizing the maximum degree

Cited in

(7)

• An algorithm for 1-bend embeddings of plane graphs in the two-dimensional grid
• Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations
• scientific article; zbMATH DE number 3646924 (Why is no real title available?)
• scientific article; zbMATH DE number 4128415 (Why is no real title available?)
• scientific article; zbMATH DE number 1500681 (Why is no real title available?)
• scientific article; zbMATH DE number 3995712 (Why is no real title available?)
• Embedding planar graphs at fixed vertex locations

This page was built for publication: A new algorithm for embedding plane graphs at fixed vertex locations

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