The Complexity of Drawing a Graph in a Polygonal Region

DOI10.7155/jgaa.00602zbMath1499.68147MaRDI QIDQ5050006

Debajyoti Mondal, Anna Lubiw, Tillmann Miltzow

Publication date: 14 November 2022

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00602

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

The complexity of the Hausdorff distance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extending convex partial drawings of graphs
• Sphere and dot product representations of graphs
• Fixed points, Nash equilibria, and the existential theory of the reals
• Convex drawings of graphs with non-convex boundary constraints
• Minimum-link watchman tours
• Some provably hard crossing number problems
• Minimum-link paths among obstacles in the plane
• On the bit complexity of minimum link paths: Superquadratic algorithms for problem solvable in linear time
• Intersection graphs of segments
• The complexity of drawing a graph in a polygonal region
• Mnëv's universality theorem revisited
• Integer realizations of disk and segment graphs
• A Kuratowski-type theorem for planarity of partially embedded graphs
• Simple realizability of complete abstract topological graphs simplified
• Variants of the segment number of a graph
• Discrete one-forms on meshes and applications to 3D mesh parameterization
• Thirty Essays on Geometric Graph Theory
• Picking Planar Edges; or, Drawing a Graph with a Planar Subgraph
• On the Complexity of the Planar Slope Number Problem
• A linear time algorithm for minimum link paths inside a simple polygon
• Who Needs Crossings? Hardness of Plane Graph Rigidity
• Convex Representations of Graphs
• The Galois Complexity of Graph Drawing: Why Numerical Solutions are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings
• Complexity of Some Geometric and Topological Problems
• Irrational Guards are Sometimes Needed
• Testing Planarity of Partially Embedded Graphs
• The Art Gallery Problem is ∃ℝ-complete
• Drawing graphs on few lines and few planes
• Complexity of Geometric k-Planarity for Fixed k
• The Complexity of Simultaneous Geometric Graph Embedding
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• How to Draw a Graph
• On the Complexity of Some Geometric Problems With Fixed Parameters
• Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area
• Graph Drawing
• Drawing Partially Embedded and Simultaneously Planar Graphs