The complexity of drawing a graph in a polygonal region
DOI10.7155/JGAA.00602zbMATH Open1499.68147OpenAlexW2788640963MaRDI QIDQ5050006FDOQ5050006
Authors: Anna Lubiw, Tillmann Miltzow, Debajyoti Mondal 
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
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 (7)
- The Galois complexity of graph drawing: why numerical solutions are ubiquitous for force-directed, spectral, and circle packing drawings
- The Galois complexity of graph drawing: why numerical solutions are ubiquitous for force-directed, spectral, and circle packing drawings
- 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)
