Output-sensitive reporting of disjoint paths

DOI10.1007/PL00009264zbMath0921.68063OpenAlexW2013491730MaRDI QIDQ1283681

Roberto Tamassia, Luca Vismara, Giuseppe Di Battista

Publication date: 30 March 1999

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/pl00009264

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items

Lower and upper bounds for long induced paths in 3-connected planar graphs ⋮ Independent spanning trees of chordal rings ⋮ Monotone Drawings of 3-Connected Plane Graphs ⋮ Minimum-segment convex drawings of 3-connected cubic plane graphs ⋮ On simultaneous straight-line grid embedding of a planar graph and its dual ⋮ Unnamed Item ⋮ Convex grid drawings of planar graphs with constant edge-vertex resolution ⋮ CONSTRAINED DISJOINT PATHS IN GEOMETRIC NETWORKS ⋮ A simple routing algorithm based on Schnyder coordinates ⋮ Linear time algorithms for two disjoint paths problems on directed acyclic graphs ⋮ Strictly-convex drawings of 3-connected planar graphs ⋮ On Representation of Planar Graphs by Segments ⋮ Drawing planar graphs with few segments on a polynomial grid ⋮ Orthogonal surfaces and their CP-orders ⋮ Multi-interval Pairwise Compatibility Graphs ⋮ On succinct greedy drawings of plane triangulations and 3-connected plane graphs ⋮ Simple computation of \textit{st}-edge- and \textit{st}-numberings from ear decompositions ⋮ Monotone drawings of graphs with few directions ⋮ Convex grid drawings of planar graphs with constant edge-vertex resolution ⋮ Mondshein Sequences (a.k.a. (2,1)-Orders) ⋮ A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths ⋮ Incremental convex planarity testing ⋮ Straight-line monotone grid drawings of series–parallel graphs