Drawing arrangement graphs in small grids, or how to play planarity

DOI10.1007/978-3-319-03841-4_38MaRDI QIDQ2867680zbMATH OpenOpenAlexFDO

Authors David Eppstein

Publication date 20 December 2013

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.0066

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Abstract: We describe a linear-time algorithm that finds a planar drawing of every graph of a simple line or pseudoline arrangement within a grid of area O(n^{7/6}). No known input causes our algorithm to use area Omega(n^{1+epsilon}) for any epsilon>0; finding such an input would represent significant progress on the famous k-set problem from discrete geometry. Drawing line arrangement graphs is the main task in the Planarity puzzle.

Recommendations

• Drawing arrangement graphs in small grids, or how to play Planarity
• scientific article; zbMATH DE number 1990911
• 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)\times (n-2)\) grid.
• An algorithm for straight-line drawing of planar graphs

Cited in

(8)

• Drawing arrangement graphs in small grids, or how to play Planarity
• What Can You Draw?
• Geometry and generation of a new graph planarity game
• A characterization of planar graphs by pseudo-line arrangements
• Removing popular faces in curve arrangements
• Aligned drawings of planar graphs
• A center transversal theorem for hyperplanes and applications to graph drawing
• Arranging solid balls to represent a graph

This page was built for publication: Drawing arrangement graphs in small grids, or how to play planarity

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