Unit-length rectangular drawings of graphs
A subgraph of a complete grid is called a grid graph. The recognition of grid graphs is NP-complete, even if restricted to trees of maximum degree three [\textit{A. Gregori}, Inf. Process. Lett. 31, No. 4, 167--173 (1989; Zbl 0672.68014)]. A similar reduction from PLANAR 3SAT shows the hardness for the restriction to biconnected plane graphs with internal faces of size four and six. Since the edges cannot be stretched, each \(C_4\) becomes a square and each \(C_6\) becomes a rectangle in every such embedding. The problem becomes solvable in polynomial time if also the external face has to become rectangular in shape and internal faces have even sizes.
- A better heuristic for orthogonal graph drawings
- A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid
- A Linear Algorithm for Bend-Optimal Orthogonal Drawings of Triconnected Cubic Plane Graphs
- Accelerated bend minimization
- Anchored drawings of planar graphs
- Checking the convexity of polytopes and the planarity of subdivisions
- Depth-First Search and Linear Graph Algorithms
- Drawing planar graphs using the canonical ordering
- Fixed edge-length graph drawing is NP-hard
- Graph Drawing
- Grid recognition: classical and parameterized computational perspectives
- Hamilton Paths in Grid Graphs
- scientific article; zbMATH DE number 2123122 (Why is no real title available?)
- scientific article; zbMATH DE number 2123123 (Why is no real title available?)
- scientific article; zbMATH DE number 3882450 (Why is no real title available?)
- scientific article; zbMATH DE number 1953108 (Why is no real title available?)
- scientific article; zbMATH DE number 2080088 (Why is no real title available?)
- scientific article; zbMATH DE number 1500675 (Why is no real title available?)
- Incremental convex planarity testing
- INNER RECTANGULAR DRAWINGS OF PLANE GRAPHS
- Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
- No-bend orthogonal drawings and no-bend orthogonally convex drawings of planar graphs (extended abstract)
- On bend-minimized orthogonal drawings of planar 3-graphs
- On Diagrams Representing Maps
- On Embedding a Graph in the Grid with the Minimum Number of Bends
- On the computational complexity of upward and rectilinear planarity testing
- On turn-regular orthogonal representations
- On Turn-Regular Orthogonal Representations
- On-line maintenance of triconnected components with SPQR-trees
- On-Line Planarity Testing
- Optimal binary space partitions for segments in the plane
- Optimal morphs of convex drawings
- Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time
- Orthogonal Drawings of Plane Graphs Without Bends
- Orthogonal Drawings of Series-Parallel Graphs with Minimum Bends
- Planar Embeddings of Graphs with Specified Edge Lengths
- Planar rectilinear drawings of outerplanar graphs in linear time
- Planar Rectilinear Drawings of Outerplanar Graphs in Linear Time
- Planar straight-line realizations of 2-trees with prescribed edge lengths
- Puzzling Grid Embeddings
- Realizability of graphs and linkages
- Rectangle and Square Representations of Planar Graphs
- Rectangular drawings of planar graphs
- Rectangular grid drawings of plane graphs
- Rectilinear Graphs and Their Embeddings
- Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time
- Simultaneous orthogonal planarity
- Spirality and Optimal Orthogonal Drawings
- Testing the planar straight-line realizability of 2-trees with prescribed edge lengths
- The complexity of minimizing wire lengths in VLSI layouts
- Unit-length embedding of binary trees on a square grid
- Unit-length rectangular drawings of graphs
- Who needs crossings? Hardness of plane graph rigidity
This page was built for publication: Unit-length rectangular drawings of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6636988)
