Linear algorithms to recognize outerplanar and maximal outerplanar graphs
From MaRDI portal
Publication:1144938
DOI10.1016/0020-0190(79)90075-9zbMath0444.68055OpenAlexW2093092867MaRDI QIDQ1144938
Publication date: 1979
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(79)90075-9
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items (46)
Planar rectilinear drawings of outerplanar graphs in linear time ⋮ Two-page book embedding of trees under vertex-neighborhood constraints ⋮ A stronger lower bound on parametric minimum spanning trees ⋮ Outer 1-planar graphs ⋮ A survey on book-embedding of planar graphs ⋮ Planar straight-line realizations of 2-trees with prescribed edge lengths ⋮ Max point-tolerance graphs ⋮ Conflict-free coloring bounds on open neighborhoods ⋮ Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth ⋮ Unnamed Item ⋮ Area-efficient planar straight-line drawings of outerplanar graphs ⋮ A connected version of the graph coloring game ⋮ Twisted ways to find plane structures in simple drawings of complete graphs ⋮ Uniquely colorable graphs up to automorphisms ⋮ An improved algorithm for finding maximum outerplanar subgraphs ⋮ Polynomial-time algorithms for special cases of the maximum confluent flow problem ⋮ Bundled crossings revisited ⋮ Naturally submodular digraphs and forbidden digraph configurations ⋮ Maximum packing for biconnected outerplanar graphs ⋮ On the order dimension of outerplanar maps ⋮ Bundled Crossings Revisited ⋮ Space-efficient biconnected components and recognition of outerplanar graphs ⋮ A stronger lower bound on parametric minimum spanning trees ⋮ Testing outerplanarity of bounded degree graphs ⋮ MAXIMAL OUTERPLANE GRAPHS WITH TWO SIMPLICIAL VERTICES ⋮ A framework and algorithms for circular drawings of graphs ⋮ A linear-time algorithm for isomorphism of a subclass of chordal graphs ⋮ Simultaneous graph embedding with bends and circular arcs ⋮ A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics ⋮ Fast detection and display of symmetry in outerplanar graphs ⋮ The Steiner forest problem revisited ⋮ Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree ⋮ On Aligned Bar 1-Visibility Graphs ⋮ Unnamed Item ⋮ Metric dimension of maximal outerplanar graphs ⋮ On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs ⋮ Subgraph isomorphism for biconnected outerplanar graphs in cubic time ⋮ The lexicographically first maximal subgraph problems:P-completeness andNC algorithms ⋮ Schematic Representation of Large Biconnected Graphs ⋮ The distance orientation problem ⋮ Heuristics for the maximum outerplanar subgraph problem ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ The subgraph isomorphism problem for outerplanar graphs ⋮ Schematic Representation of Biconnected Graphs ⋮ A linear-time certifying algorithm for recognizing generalized series-parallel graphs ⋮ An \(O( mn^2)\) algorithm for computing the strong geodetic number in outerplanar graphs
Cites Work
This page was built for publication: Linear algorithms to recognize outerplanar and maximal outerplanar graphs
