Snapping graph drawings to the grid optimally

DOI10.1007/978-3-319-50106-2_12MaRDI QIDQ2961511zbMATH OpenOpenAlexFDO

Authors Andre Löffler, Thomas C. van Dijk, Alexander Wolff

Publication date 21 February 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Integer programming (90C10)

Abstract: In geographic information systems and in the production of digital maps for small devices with restricted computational resources one often wants to round coordinates to a rougher grid. This removes unnecessary detail and reduces space consumption as well as computation time. This process is called snapping to the grid and has been investigated thoroughly from a computational-geometry perspective. In this paper we investigate the same problem for given drawings of planar graphs under the restriction that their combinatorial embedding must be kept and edges are drawn straight-line. We show that the problem is NP-hard for several objectives and provide an integer linear programming formulation. Given a plane graph G and a positive integer w, our ILP can also be used to draw G straight-line on a grid of width w and minimum height (if possible).

Recommendations

• Minimizing the Area for Planar Straight-Line Grid Drawings
• scientific article; zbMATH DE number 432759
• scientific article; zbMATH DE number 1342138
• SOFSEM 2005: Theory and Practice of Computer Science
• How to draw a planar graph on a grid

Cites work

• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• An intersection-sensitive algorithm for snap rounding
• Feasibility and infeasibility in optimization. Algorithms and computational methods.
• How to Draw a Graph
• How to draw a planar graph on a grid
• Incremental grid-like layout using soft and hard constraints
• Minimizing the Area for Planar Straight-Line Grid Drawings
• Minimum-width grid drawings of plane graphs
• Optimal binary space partitions for segments in the plane
• Rounding Arrangements Dynamically
• Snapping graph drawings to the grid optimally

Cited in

(3)

• Snapping graph drawings to the grid optimally
• GRIP: Graph Drawing with Intelligent Placement
• Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings

This page was built for publication: Snapping graph drawings to the grid optimally

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