Output-sensitive reporting of disjoint paths

DOI10.1007/PL00009264MaRDI QIDQ1283681zbMATH OpenOpenAlexFDO

Authors Roberto Tamassia, Giuseppe Di Battista, Luca Vismara

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

Recommendations

• Reconstructing edge-disjoint paths faster
• A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs
• On shortest disjoint paths in planar graphs
• Algorithms and Computation
• On shortest disjoint paths in planar graphs

Cited in

(29)

• A simple routing algorithm based on Schnyder coordinates
• A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths
• Simple computation of \textit{st}-edge- and \textit{st}-numberings from ear decompositions
• Output-sensitive reporting of disjoint paths (extended abstract)
• Monotone drawings of 3-connected plane graphs
• CONSTRAINED DISJOINT PATHS IN GEOMETRIC NETWORKS
• \((t, s)\)-completely independent spanning trees
• Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
• On simultaneous straight-line grid embedding of a planar graph and its dual
• Straight-line monotone grid drawings of series-parallel graphs
• Lower and upper bounds for long induced paths in 3-connected planar graphs
• Reconstructing edge-disjoint paths faster
• Independent spanning trees of chordal rings
• Mondshein sequences (a.k.a. (2,1)-orders)
• Minimum-segment convex drawings of 3-connected cubic plane graphs
• On Representation of Planar Graphs by Segments
• A Schnyder-type drawing algorithm for 5-connected triangulations
• Multi-interval pairwise compatibility graphs (extended abstract)
• Linear time algorithms for two disjoint paths problems on directed acyclic graphs
• On succinct greedy drawings of plane triangulations and 3-connected plane graphs
• Convex grid drawings of planar graphs with constant edge-vertex resolution
• Structural parameters of Schnyder woods
• scientific article; zbMATH DE number 1372667 (Why is no real title available?)
• Strictly-convex drawings of 3-connected planar graphs
• Drawing planar graphs with few segments on a polynomial grid
• Orthogonal surfaces and their CP-orders
• Incremental convex planarity testing
• Convex grid drawings of planar graphs with constant edge-vertex resolution
• Monotone drawings of graphs with few directions

This page was built for publication: Output-sensitive reporting of disjoint paths

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