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

DOI10.1007/978-3-319-03841-4_38zbMATH Open1406.68074arXiv1308.0066OpenAlexW1503918231MaRDI QIDQ2867680FDOQ2867680

Authors: David Eppstein 

Publication date: 20 December 2013

Published in: Graph Drawing (Search for Journal in Brave)

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.

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

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

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)

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)