The complexity of drawing a graph in a polygonal region

DOI10.7155/JGAA.00602zbMATH Open1499.68147OpenAlexW2788640963MaRDI QIDQ5050006FDOQ5050006

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

Recommendations

• The complexity of drawing a graph in a polygonal region
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• Graph Drawing
• On the complexity of some geometric problems with fixed parameters
• Drawing planar graphs on points inside a polygon

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

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

Cited In (5)

• Framework for \(\exists\mathbb{R}\)-completeness of two-dimensional packing problems
• On classifying continuous constraint satisfaction problems
• The complexity of the Hausdorff distance
• Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
• The complexity of drawing graphs on few lines and few planes

This page was built for publication: The complexity of drawing a graph in a polygonal region

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