The partial visibility representation extension problem

DOI10.1007/s00453-017-0322-4zbMath1392.68322arXiv1512.00174OpenAlexW2962960836WikidataQ59528970 ScholiaQ59528970MaRDI QIDQ724235

Steven Chaplick, Grzegorz Guśpiel, Grzegorz Gutowski, Giuseppe Liotta, Tomasz Krawczyk

Publication date: 25 July 2018

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

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

zbMATH Keywords

planar graphsNP-completenesspartial representation extensionbar visibilitySPQR-treesst-ordering

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Simple algorithms for partial and simultaneous rectangular duals with given contact orientations ⋮ Extending partial representations of interval graphs ⋮ Combinatorial properties and recognition of unit square visibility graphs ⋮ Extending partial representations of rectangular duals with given contact orientations ⋮ Colored anchored visibility representations in 2D and 3D space ⋮ Minimal obstructions for partial representations of interval graphs ⋮ Extending upward planar graph drawings ⋮ Unnamed Item ⋮ The partial visibility representation extension problem ⋮ Unnamed Item ⋮ Inserting one edge into a simple drawing is hard ⋮ Beyond Clustered Planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Area requirement of visibility representations of trees
• Compact visibility representation of 4-connected plane graphs
• Recognition and complexity of point visibility graphs
• Extending partial representations of proper and unit interval graphs
• Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs
• A linear-time algorithm for drawing a planar graph on a grid
• A polynomial time circle packing algorithm
• The partial visibility representation extension problem
• How to draw a planar graph on a grid
• Representing a planar graph by vertical lines joining different levels
• A unified approach to visibility representations of planar graphs
• A note on visibility graphs
• Making data structures persistent
• Algorithms for plane representations of acyclic digraphs
• On grid intersection graphs
• Area requirement and symmetry display of planar upward drawings
• Some results on visibility graphs
• Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
• Upward planarity testing
• Extending partial representations of subclasses of chordal graphs
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• Drawing Trees, Outerplanar Graphs, Series-Parallel Graphs, and Planar Graphs in a Small Area
• Extending Partial Representations of Circle Graphs
• Contact Representations of Planar Graphs: Extending a Partial Representation is Hard
• Visibility Representation of Plane Graphs with Simultaneous Bound for Both Width and Height
• On minimal-node-cost planar embeddings
• Optimal Binary Space Partitions in the Plane
• On Triangle Contact Graphs
• On-Line Planarity Testing
• Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
• OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
• The Bar Visibility Number of a Graph
• Unsolved problems in visibility graphs of points, segments, and polygons
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• Partial orders of dimension 2

This page was built for publication: The partial visibility representation extension problem