License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2018.10
URL: http://drops.dagstuhl.de/opus/volltexte/2018/8699/
Go to the corresponding LIPIcs Volume Portal


Akutsu, Tatsuya ; de la Higuera, Colin ; Tamura, Takeyuki

A Simple Linear-Time Algorithm for Computing the Centroid and Canonical Form of a Plane Graph and Its Applications

pdf-format:
LIPIcs-CPM-2018-10.pdf (0.5 MB)


Abstract

We present a simple linear-time algorithm for computing the topological centroid and the canonical form of a plane graph. Although the targets are restricted to plane graphs, it is much simpler than the linear-time algorithm by Hopcroft and Wong for determination of the canonical form and isomorphism of planar graphs. By utilizing a modified centroid for outerplanar graphs, we present a linear-time algorithm for a geometric version of the maximum common connected edge subgraph (MCCES) problem for the special case in which input geometric graphs have outerplanar structures, MCCES can be obtained by deleting at most a constant number of edges from each input graph, and both the maximum degree and the maximum face degree are bounded by constants.

BibTeX - Entry

@InProceedings{akutsu_et_al:LIPIcs:2018:8699,
  author =	{Tatsuya Akutsu and Colin de la Higuera and Takeyuki Tamura},
  title =	{{A Simple Linear-Time Algorithm for Computing the Centroid and Canonical Form of a Plane Graph and Its Applications}},
  booktitle =	{Annual Symposium on Combinatorial Pattern Matching  (CPM 2018)},
  pages =	{10:1--10:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-074-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{105},
  editor =	{Gonzalo Navarro and David Sankoff and Binhai Zhu},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8699},
  doi =		{10.4230/LIPIcs.CPM.2018.10},
  annote =	{Keywords: Plane graph, Graph isomorphism, Maximum common subgraph}
}

Keywords: Plane graph, Graph isomorphism, Maximum common subgraph
Seminar: Annual Symposium on Combinatorial Pattern Matching (CPM 2018)
Issue Date: 2018
Date of publication: 11.05.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI