On Embedding a Graph in the Grid with the Minimum Number of Bends
From MaRDI portal
Publication:3801098
DOI10.1137/0216030zbMath0654.68090OpenAlexW2002025203MaRDI QIDQ3801098
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
Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Computing methodologies and applications (68U99) Planar graphs; geometric and topological aspects of graph theory (05C10) Applications of graph theory to circuits and networks (94C15)
Related Items (only showing first 100 items - show all)
Advances on Testing C-Planarity of Embedded Flat Clustered Graphs ⋮ Computing orthogonal drawings with the minimum number of bends ⋮ Orthogonal drawing of high degree graphs with small area and few bends ⋮ Computing bend-minimum orthogonal drawings of plane series-parallel graphs in linear time ⋮ Planar Confluent Orthogonal Drawings of 4-Modal Digraphs ⋮ The Complexity of Angular Resolution ⋮ Planar confluent orthogonal drawings of 4-modal digraphs ⋮ Unit-length rectangular drawings of graphs ⋮ Rectilinear planarity of partial 2-trees ⋮ Rectilinear Planarity of Partial 2-Trees ⋮ A topology-shape-metrics framework for ortho-radial graph drawing ⋮ An annotated review on graph drawing and its applications ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Extending upward planar graph drawings ⋮ Simultaneous Embeddings with Few Bends and Crossings ⋮ How to Draw a Planarization ⋮ The DFS-heuristic for orthogonal graph drawing ⋮ On the complexity of orthogonal compaction ⋮ Universal slope sets for upward planar drawings ⋮ Greedy rectilinear drawings ⋮ Universal slope sets for upward planar drawings ⋮ Greedy rectilinear drawings ⋮ Level-planar drawings with few slopes ⋮ Accelerated Bend Minimization ⋮ INNER RECTANGULAR DRAWINGS OF PLANE GRAPHS ⋮ Orthogonal layout with optimal face complexity ⋮ On orthogonally convex drawings of plane graphs ⋮ Planar rectilinear drawings of outerplanar graphs in linear time ⋮ Minimum rectilinear polygons for given angle sequences ⋮ The complexity of Snake and undirected NCL variants ⋮ How to draw the minimum cuts of a planar graph ⋮ Relating bends and size in orthogonal graph drawings ⋮ HV-planarity: algorithms and complexity ⋮ On Turn-Regular Orthogonal Representations ⋮ Planar L-Drawings of Bimodal Graphs ⋮ Optimal orthogonal drawings of triconnected plane graphs ⋮ An efficient parallel algorithm for finding rectangular duals of plane triangular graphs ⋮ Single bend wiring on surfaces ⋮ The techniques of Komolgorov and Bardzin for three-dimensional orthogonal graph drawings ⋮ Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs (extended abstract) ⋮ SIMULTANEOUS EMBEDDING OF EMBEDDED PLANAR GRAPHS ⋮ Efficient automated schematic map drawing using multiobjective mixed integer programming ⋮ A note on 3D orthogonal drawings with direction constrained edges ⋮ Orthogeodesic point-set embedding of trees ⋮ Embedding rectilinear graphs in linear time ⋮ Graph Compact Orthogonal Layout Algorithm ⋮ Extending Partial Orthogonal Drawings ⋮ Upward planar drawings with two slopes ⋮ Drawing planar graphs using the canonical ordering ⋮ Algorithms for plane representations of acyclic digraphs ⋮ A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid ⋮ New results on drawing angle graphs ⋮ Algorithms for area-efficient orthogonal drawing ⋮ A better heuristic for orthogonal graph drawings ⋮ Vertex Contact Graphs of Paths on a Grid ⋮ Bend-optimal orthogonal graph drawing in the general position model ⋮ Orthogonal Graph Drawing with Inflexible Edges ⋮ A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system ⋮ Universal slope sets for 1-bend planar drawings ⋮ Planar Open Rectangle-of-Influence Drawings with Non-aligned Frames ⋮ Overloaded Orthogonal Drawings ⋮ Hardness of Approximate Compaction for Nonplanar Orthogonal Graph Drawings ⋮ Rectangular grid drawings of plane graphs ⋮ Shortest path embeddings of graphs on surfaces ⋮ The shape of orthogonal cycles in three dimensions ⋮ Minimum Rectilinear Polygons for Given Angle Sequences ⋮ On the Density of Non-simple 3-Planar Graphs ⋮ Simultaneous Orthogonal Planarity ⋮ Schnyder decompositions for regular plane graphs and application to drawing ⋮ How to Draw a Planarization ⋮ Sketched representations and orthogonal planarity of bounded treewidth graphs ⋮ Bend-optimal orthogonal drawings of triconnected plane graphs ⋮ THE THREE-PHASE METHOD: A UNIFIED APPROACH TO ORTHOGONAL GRAPH DRAWING ⋮ On the area requirements of planar straight-line orthogonal drawings of ternary trees ⋮ Bend-minimum orthogonal drawings in quadratic time ⋮ Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Orthogonal graph drawing with flexibility constraints ⋮ Lower bounds for planar orthogonal drawings of graphs ⋮ Modifying orthogonal drawings for label placement ⋮ On smooth orthogonal and octilinear drawings: relations, complexity and Kandinsky drawings ⋮ Area requirement and symmetry display of planar upward drawings ⋮ Unnamed Item ⋮ Closed, oriented, connected 3-manifolds are subtle equivalence classes of plane graphs ⋮ Orthogonal graph drawing with inflexible edges ⋮ Finding a minimum medial axis of a discrete shape is NP-hard ⋮ Embedding-preserving rectangle visibility representations of nonplanar graphs ⋮ Complexity results for three-dimensional orthogonal graph drawing ⋮ Strip planarity testing for embedded planar graphs ⋮ An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains ⋮ Upward drawings of triconnected digraphs. ⋮ Drawing orders using less ink ⋮ An experimental comparison of four graph drawing algorithms. ⋮ Square-Orthogonal Drawing with Few Bends per Edge ⋮ PSPACE-completeness of an escape problem ⋮ On embedding a graph in the grid with the maximum number of bends and other bad features ⋮ Schematization of networks ⋮ An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT ⋮ Edge intersection graphs of single bend paths on a grid
This page was built for publication: On Embedding a Graph in the Grid with the Minimum Number of Bends
