Non-aligned drawings of planar graphs

DOI10.1007/978-3-319-50106-2_11MaRDI QIDQ2961510zbMATH OpenOpenAlexFDO

Authors Claire Pennarun, Therese Biedl

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/1606.02220

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (including graph drawing) in computer science (68R10)

Abstract: A non-aligned drawing of a graph is a drawing where no two vertices are in the same row or column. Auber et al. showed that not all planar graphs have non-aligned drawings that are straight-line, planar, and in the minimal-possible $nimesn$-grid. They also showed that such drawings exist if up to $n-3$ edges may have a bend. In this paper, we give algorithms for non-aligned planar drawings that improve on the results by Auber et al. In particular, we give such drawings in an $nimesn$-grid with significantly fewer bends, and we study what grid-size can be achieved if we insist on having straight-line drawings.

Recommendations

• Non-aligned drawings of planar graphs
• Aligned drawings of planar graphs
• Aligned drawings of planar graphs
• Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs
• Drawing non-planar graphs with crossing-free subgraphs

Cites work

• Approximation algorithms for NP-complete problems on planar graphs
• Arc diagrams, flip distances, and Hamiltonian triangulations
• Drawing planar graphs with many collinear vertices
• Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
• Faster scaling algorithms for general graph matching problems
• How to draw a planar graph on a grid
• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• scientific article; zbMATH DE number 1500691 (Why is no real title available?)
• On triangulating planar graphs under the four-connectivity constraint
• Planar Open Rectangle-of-Influence Drawings with Non-aligned Frames
• Rook-Drawing for Plane Graphs
• The (3,1)-ordering for 4-connected planar triangulations
• The rectangle of influence drawability problem

Cited in

(6)

• Planar Open Rectangle-of-Influence Drawings with Non-aligned Frames
• Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way
• Aligned drawings of planar graphs
• Aligned drawings of planar graphs
• Non-aligned drawings of planar graphs
• Simplifying Non-Simple Fan-Planar Drawings

This page was built for publication: Non-aligned drawings of planar graphs

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