A 1.235 lower bound on the number of points needed to draw alln-vertex planar graphs

DOI10.1016/j.ipl.2004.06.009zbMath1183.68430OpenAlexW2076787978WikidataQ59410433 ScholiaQ59410433MaRDI QIDQ834906

Maciej Kurowski

Publication date: 27 August 2009

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.06.009

zbMATH Keywords

combinatorial problemsgraph drawinguniversal set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (13)

Universal sets of \(n\) points for one-bend drawings of planar graphs with \(n\) vertices ⋮ Upward Straight-Line Embeddings of Directed Graphs into Point Sets ⋮ Orthogeodesic Point-Set Embedding of Trees ⋮ On Point-Sets That Support Planar Graphs ⋮ Small Point Sets for Simply-Nested Planar Graphs ⋮ An exponential bound for simultaneous embeddings of planar graphs ⋮ A Note on Universal Point Sets for Planar Graphs ⋮ A note on universal point sets for planar graphs ⋮ Small universal point sets for \(k\)-outerplanar graphs ⋮ Universal point sets for planar three-trees ⋮ Every collinear set in a planar graph is free ⋮ Upward straight-line embeddings of directed graphs into point sets ⋮ Plane 3-Trees: Embeddability and Approximation

Cites Work

• A linear-time algorithm for drawing a planar graph on a grid
• Drawing plane graphs nicely
• How to draw a planar graph on a grid
• Grid embedding of 4-connected plane graphs
• Bemerkungen zum Vierfarbenproblem
• Convex Maps
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A 1.235 lower bound on the number of points needed to draw alln-vertex planar graphs