A simple linear-time algorithm for computing the centroid and canonical form of a plane graph and its applications
From MaRDI portal
Publication:5140773
DOI10.4230/LIPICS.CPM.2018.10zbMATH Open1497.68361MaRDI QIDQ5140773FDOQ5140773
Authors: Tatsuya Akutsu, Colin de la Higuera, Takeyuki Tamura 
Publication date: 16 December 2020
Recommendations
- A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree
- A linear algorithm for the maximal planar subgraph problem
- A polynomial-time algorithm for computing the maximum common subgraph of outerplanar graphs of bounded degree
- A Linear-Time Algorithm for Finding a Maximal Planar Subgraph
- A linear time algorithm for finding maximal planar subgraphs
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- A bisection algorithm for grammar-based compression of ordered trees
- Lexicographically least circular substrings
- Optimal algorithms for computing the canonical form of a circular string
- A V log V algorithm for isomorphism of triconnected planar graphs
- Graph isomorphism in quasipolynomial time (extended abstract)
- An n log n algorithm for determining the congruity of polyhedra
- Fast detection and display of symmetry in outerplanar graphs
- On the complexity of submap isomorphism and maximum common submap problems
- On maximum common subgraph problems in series-parallel graphs
- On the complexity of the maximum common subgraph problem for partial \(k\)-trees of bounded degree
- Maximum common induced subgraph parameterized by vertex cover
This page was built for publication: A simple linear-time algorithm for computing the centroid and canonical form of a plane graph and its applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140773)
