A unified approach to visibility representations of planar graphs

From MaRDI portal

Publication:1085167

Jump to:navigation, search

DOI10.1007/BF02187705zbMath0607.05026MaRDI QIDQ1085167

Roberto Tamassia, Ioannis. G. Tollis

Publication date: 1986

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131000

zbMATH Keywords

planar graphs visibility representations planar layout

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

Orthogonal polygon reconstruction from stabbing information ⋮ Visibility representations of boxes in 2.5 dimensions ⋮ Bar visibility numbers for hypercubes and outerplanar digraphs ⋮ Area requirement of visibility representations of trees ⋮ Visibility representations of four-connected plane graphs with near optimal heights ⋮ Simultaneous visibility representations of plane \(st\)-graphs using L-shapes ⋮ A left-first search algorithm for planar graphs ⋮ An efficient parallel algorithm for finding rectangular duals of plane triangular graphs ⋮ How to draw a series-parallel digraph ⋮ 3-coloring arrangements of line segments with 4 slopes is hard ⋮ The strength of weak proximity ⋮ Optimal-area visibility representations of outer-1-plane graphs ⋮ Visibility graphs of staircase polygons and the weak Bruhat order. I: From visibility graphs to maximal chains ⋮ Rectangle-visibility representations of bipartite graphs ⋮ Art gallery problem with rook and queen vision ⋮ Computing orthogonal drawings with the minimum number of bends ⋮ Determining bar-representability for ordered weighted graphs ⋮ Drawing planar graphs using the canonical ordering ⋮ An annotated bibliography on 1-planarity ⋮ Skyscraper polytopes and realizations of plane triangulations ⋮ Algorithms for plane representations of acyclic digraphs ⋮ A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid ⋮ Unit hypercube visibility numbers of trees ⋮ New results on drawing angle graphs ⋮ Universal 3-dimensional visibility representations for graphs ⋮ Alternating paths along axis-parallel segments ⋮ Trapezoidal diagrams, upward triangulations, and prime Catalan numbers ⋮ A tribute to Frank Harary (in honor of his 70th birthday) ⋮ Special graph representation and visualization of semantic networks ⋮ Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems ⋮ Upper bounds for bar visibility of subgraphs and \(n\)-vertex graphs ⋮ Good spanning trees in graph drawing ⋮ On the Number of α-Orientations ⋮ 1-Bend Upward Planar Drawings of SP-Digraphs ⋮ On Representation of Planar Graphs by Segments ⋮ L-visibility drawings of IC-planar graphs ⋮ Bijections for Baxter families and related objects ⋮ \(\mathsf{T}\)-shape visibility representations of 1-planar graphs ⋮ Colored anchored visibility representations in 2D and 3D space ⋮ 1-bend upward planar slope number of SP-digraphs ⋮ Homotopy height, grid-major height and graph-drawing height ⋮ Dynamic maintenance of planar digraphs, with applications ⋮ Compact visibility representation of 4-connected plane graphs ⋮ Orthogonal drawings based on the stratification of planar graphs ⋮ On Guarding Orthogonal Polygons with Sliding Cameras ⋮ THE THREE-PHASE METHOD: A UNIFIED APPROACH TO ORTHOGONAL GRAPH DRAWING ⋮ DRAWING DIRECTED ACYCLIC GRAPHS: AN EXPERIMENTAL STUDY ⋮ Not being (super)thin or solid is hard: A study of grid Hamiltonicity ⋮ Grid-Obstacle Representations with Connections to Staircase Guarding ⋮ Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Simultaneous visibility representations of undirected pairs of graphs ⋮ Large Angle Crossing Drawings of Planar Graphs in Subquadratic Area ⋮ Constrained visibility representations of graphs ⋮ A linear-time algorithm for drawing a planar graph on a grid ⋮ A note on the combinatorial structure of the visibility graph in simple polygons ⋮ Area requirement and symmetry display of planar upward drawings ⋮ Directed rectangle-visibility graphs have unbounded dimension ⋮ Unnamed Item ⋮ Constructing compact rectilinear planar layouts using canonical representation of planar graphs ⋮ Embedding-preserving rectangle visibility representations of nonplanar graphs ⋮ Computing the full visibility graph of a set of line segments ⋮ Every plane graph is facially-non-repetitively \(C\)-choosable ⋮ Dynamic reachability in planar digraphs with one source and one sink ⋮ On the number of upward planar orientations of maximal planar graphs ⋮ Some results on visibility graphs ⋮ Algorithms for computing a parameterized \(st\)-orientation ⋮ Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation ⋮ Upward drawings of triconnected digraphs. ⋮ An experimental comparison of four graph drawing algorithms. ⋮ A note on rectilinear and polar visibility graphs ⋮ Improved visibility representation of plane graphs ⋮ NP-completeness of st-orientations for plane graphs ⋮ POINT AND LINE SEGMENT RECONSTRUCTION FROM VISIBILITY INFORMATION ⋮ Grid intersection graphs and order dimension ⋮ On triangulating planar graphs under the four-connectivity constraint ⋮ Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings ⋮ Planar bus graphs ⋮ The partial visibility representation extension problem ⋮ Ortho-polygon visibility representations of embedded graphs ⋮ Visibility Representations of Four-Connected Plane Graphs with Near Optimal Heights ⋮ Base-object location problems for base-monotone regions ⋮ Three Results on Frequency Assignment in Linear Cellular Networks ⋮ Linear bound on extremal functions of some forbidden patterns in 0-1 matrices ⋮ Classes and recognition of curve contact graphs ⋮ Simultaneous Visibility Representations of Plane st-graphs Using L-shapes ⋮ Optimal \(st\)-orientations for plane triangulations ⋮ Algorithms for Drawing Planar p-petal Graphs ⋮ Combinatorial characterization of upward planarity ⋮ On 3D visibility representations of graphs with few crossings per edge ⋮ Three-dimensional orthogonal graph drawing algorithms ⋮ Advances in the theory and practice of graph drawing ⋮ Bijective counting of plane bipolar orientations and Schnyder woods ⋮ Three results on frequency assignment in linear cellular networks ⋮ Visibility representation of plane graphs via canonical ordering tree ⋮ Drawing series parallel digraphs symmetrically ⋮ Edge Partitions and Visibility Representations of 1-planar Graphs ⋮ Bipolar orientations revisited ⋮ How to draw a planar graph on a grid ⋮ RECTANGLE AND BOX VISIBILITY GRAPHS IN 3D ⋮ Combinatorial properties and recognition of unit square visibility graphs ⋮ Bitonic \(st\)-orderings for upward planar graphs: splits and bends in the variable embedding scenario ⋮ Area, perimeter, height, and width of rectangle visibility graphs ⋮ A more compact visibility representation ⋮ Visibility representations of toroidal and Klein-bottle graphs ⋮ Sliding column model for t-unit bar visibility representations of graphs ⋮ Defying gravity and gadget numerosity: the complexity of the Hanano puzzle ⋮ Two algorithms for finding rectangular duals of planar graphs ⋮ Width-Optimal Visibility Representations of Plane Graphs ⋮ On the Bar Visibility Number of Complete Bipartite Graphs ⋮ The DFS-heuristic for orthogonal graph drawing ⋮ Edge partitions of optimal 2-plane and 3-plane graphs ⋮ Ortho-polygon visibility representations of 3-connected 1-plane graphs ⋮ Upward planar morphs ⋮ On Aligned Bar 1-Visibility Graphs ⋮ Drawing Planar Graphs with Reduced Height ⋮ Unnamed Item ⋮ AN APPLICATION OF WELL-ORDERLY TREES IN GRAPH DRAWING

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1085167&oldid=13114853"