On Embedding a Graph in the Grid with the Minimum Number of Bends

DOI10.1137/0216030MaRDI QIDQ3801098zbMATH OpenOpenAlexFDO

Authors Roberto Tamassia

Publication date 1987

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0216030

zbMATH Keywords

network flowplanar embeddingbendsVLSI circuit layoutrectilinear grid

Mathematics Subject Classification ID

Computing methodologies and applications (68U99) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Planar graphs; geometric and topological aspects of graph theory (05C10) Applications of graph theory to circuits and networks (94C15)

Recommendations

• On minimal-node-cost planar embeddings
• Drawing graphs on rectangular grids
• General theoretical results on rectilinear embeddability of graphs
• Rectilinear Graphs and Their Embeddings
• scientific article; zbMATH DE number 432759

Cited in

(only showing first 100 items - show all)

• Finding a minimum medial axis of a discrete shape is NP-hard
• Towards area requirements for drawing hierarchically planar graphs
• Minimum rectilinear polygons for given angle sequences
• Embedding-preserving rectangle visibility representations of nonplanar graphs
• Universal slope sets for 1-bend planar drawings
• Octagonal drawings of plane graphs with prescribed face areas
• Minimum rectilinear polygons for given angle sequences
• Rectilinear-upward planarity testing of digraphs
• Ortho-radial drawing in near-linear time
• Algorithms for Drawing Planar p-petal Graphs
• The efficient recognition on net-extensibility of graphs
• Bend-minimum orthogonal drawings in quadratic time
• Planar L-Drawings of Bimodal Graphs
• Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
• Vertex contact graphs of paths on a grid
• Graph compact orthogonal layout algorithm
• Orthogonal planarity testing of bounded treewidth graphs
• Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity
• The shape of orthogonal cycles in three dimensions
• Proper colorability of segment intersection graphs
• Upward drawings of triconnected digraphs.
• The complexity of iterated reversible computation
• The techniques of Komolgorov and Bardzin for three-dimensional orthogonal graph drawings
• Rectilinear Planarity of Partial 2-Trees
• Orthogonal layout with optimal face complexity
• On turn-regular orthogonal representations
• Modifying orthogonal drawings for label placement
• PSPACE-completeness of an escape problem
• Rikudo is NP-complete
• On Embedding a Graph in the Grid with the Maximum Number of Bends and Other Bad Features
• On the area requirements of planar straight-line orthogonal drawings of ternary trees
• An annotated review on graph drawing and its applications
• Planar Confluent Orthogonal Drawings of 4-Modal Digraphs
• Greedy rectilinear drawings
• Greedy rectilinear drawings
• How to draw the minimum cuts of a planar graph
• INNER RECTANGULAR DRAWINGS OF PLANE GRAPHS
• Planar L-drawings of directed graphs
• Planar confluent orthogonal drawings of 4-modal digraphs
• Accelerated bend minimization
• Planar L-drawings of bimodal graphs
• The complexity of Snake and undirected NCL variants
• Embedding rectilinear graphs in linear time
• Universal slope sets for upward planar drawings
• Orthogeodesic point-set embedding of trees
• HV-planarity: algorithms and complexity
• Complexity results for three-dimensional orthogonal graph drawing
• An efficient parallel algorithm for finding rectangular duals of plane triangular graphs
• Simultaneous orthogonal planarity
• A census of graph-drawing algorithms based on generalized transversal structures
• Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time
• Bend complexity and Hamiltonian cycles in grid graphs
• Square-orthogonal drawing with few bends per edge
• Optimal orthogonal drawings of triconnected plane graphs
• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• Orthogonal drawing of high degree graphs with small area and few bends
• Relating bends and size in orthogonal graph drawings
• Graph layout for applications in compiler construction
• scientific article; zbMATH DE number 1858605 (Why is no real title available?)
• New results on drawing angle graphs
• Planar Rectilinear Drawings of Outerplanar Graphs in Linear Time
• Drawing graphs on rectangular grids
• Computing orthogonal drawings with the minimum number of bends
• Automated rendering of multi-stranded DNA complexes with pseudoknots
• Bend-optimal orthogonal graph drawing in the general position model
• Orthogonal graph drawing with flexibility constraints
• Closed, oriented, connected 3-manifolds are subtle equivalence classes of plane graphs
• Rectangular grid drawings of plane graphs
• Orthogonal graph drawing with inflexible edges
• Orthogonal graph drawing with inflexible edges
• Embedding problems for paths with direction constrained edges.
• Lower bounds for planar orthogonal drawings of graphs
• Overloaded orthogonal drawings
• Orthogonal drawings of graphs with vertex and edge labels
• Extending partial orthogonal drawings
• An Integer-Linear Program for Bend-Minimization in Ortho-Radial Drawings
• On Turn-Regular Orthogonal Representations
• The Turing Test for Graph Drawing Algorithms
• Simultaneous embedding of embedded planar graphs
• On the complexity of orthogonal compaction
• Unit-length rectangular drawings of graphs
• How to draw a planarization
• A Schnyder-type drawing algorithm for 5-connected triangulations
• Area requirement and symmetry display of planar upward drawings
• Non-planar square-orthogonal drawing with few-bend edges
• The DFS-heuristic for orthogonal graph drawing
• A simple pipeline for orthogonal graph drawing
• On the parameterized complexity of bend-minimum orthogonal planarity
• Upward and orthogonal planarity are W[1]-hard parameterized by treewidth
• On orthogonally convex drawings of plane graphs
• Approximation Algorithms for Facial Cycles in Planar Embeddings
• Weakly leveled planarity with bounded span
• NP-completeness for minimizing maximum edge length in grid embeddings
• scientific article; zbMATH DE number 7765366 (Why is no real title available?)
• Planar Open Rectangle-of-Influence Drawings with Non-aligned Frames
• Advances in the theory and practice of graph drawing
• Three-dimensional orthogonal graph drawing algorithms
• On the parameterized complexity of bend-minimum orthogonal planarity
• Grid straight-line embeddings of trees with a minimum number of bends per path
• On the density of non-simple 3-planar graphs

This page was built for publication: On Embedding a Graph in the Grid with the Minimum Number of Bends

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