Top

Published in:

2020 | OriginalPaper | Chapter

Implicit Enumeration of Topological-Minor-Embeddings and Its Application to Planar Subgraph Enumeration

Authors : Yu Nakahata, Jun Kawahara, Takashi Horiyama, Shin-ichi Minato

Published in: WALCOM: Algorithms and Computation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Given graphs G and H, we propose a method to implicitly enumerate topological-minor-embeddings of H in G using decision diagrams. We show a useful application of our method to enumerating subgraphs characterized by forbidden topological minors, that is, planar, outerplanar, series-parallel, and cactus subgraphs. Computational experiments show that our method can find all planar subgraphs in a given graph at most five orders of magnitude faster than a naive backtracking-based method.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Packing and Covering with Segments

next chapter Partitioning a Graph into Complementary Subgraphs

In another definition, F is homeomorphic to H if some subdivision of F is isomorphic to some subdivision of H. However, we allow subdividing only for H because H is “contracted enough” when it is a forbidden topological minor, that is, H does not contain redundant vertices with degree 2.

To avoid confusion, we use the terms “node” and “arc” for a \((c+1)\)-DD and use “vertex” and “edge” for an input graph.

http://www.graphdrawing.org/data.html.

https://www.boost.org/doc/libs/1_71_0/libs/graph/doc/boyer_myrvold.html.

Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics (1999)

Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C–35(8), 677–691 (1986)CrossRef

Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012)MATH

Horiyama, T., Kawahara, J., ichi Minato, S., Nakahata, Y.: Decomposing a graph into unigraphs (2019). arXiv:1904.09438

Inoue, T., Iwashita, H., Kawahara, J., Minato, S.: Graphillion: software library for very large sets of labeled graphs. Int. J. Softw. Tools Technol. Transfer 18(1), 57–66 (2016)CrossRef

Iwashita, H., Minato, S.: Efficient top-down ZDD construction techniques using recursive specifications. TCS Technical Reports TCS-TR-A-13-69, pp. 1–28 (2013)

Kawahara, J., Inoue, T., Iwashita, H., Minato, S.: Frontier-based search for enumerating all constrained subgraphs with compressed representation. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E100–A(9), 1773–1784 (2017)CrossRef

Kawahara, J., Saitoh, T., Suzuki, H., Yoshinaka, R.: Colorful frontier-based search: implicit enumeration of chordal and interval subgraphs. In: Kotsireas, I., Pardalos, P., Parsopoulos, K.E., Souravlias, D., Tsokas, A. (eds.) SEA 2019. LNCS, vol. 11544, pp. 125–141. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34029-2_9CrossRef

Knuth, D.E.: The Art of Computer Programming. Combinatorial Algorithms, Part 1, vol. 4A, 1st edn. Addison-Wesley Professional, Boston (2011)MATH

10.

Kuratowski, C.: Sur le problème des courbes gauches en topologie. Fundamenta Mathematicae 15(1), 271–283 (1930)MathSciNetCrossRef

11.

Minato, S.: Zero-suppressed BDDs for set manipulation in combinatorial problems. In: Proceedings of the 30th ACM/IEEE Design Automation Conference (DAC 1993), pp. 272–277. ACM, New York (1993)

12.

Nakahata, Y., Kawahara, J., Horiyama, T., Kasahara, S.: Enumerating all spanning shortest path forests with distance and capacity constraints. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E101–A(9), 1363–1374 (2018)CrossRef

13.

Sekine, K., Imai, H., Tani, S.: Computing the Tutte polynomial of a graph of moderate size. In: Staples, J., Eades, P., Katoh, N., Moffat, A. (eds.) ISAAC 1995. LNCS, vol. 1004, pp. 224–233. Springer, Heidelberg (1995). https://doi.org/10.1007/BFb0015427CrossRef

Title: Implicit Enumeration of Topological-Minor-Embeddings and Its Application to Planar Subgraph Enumeration
Authors: Yu Nakahata
Jun Kawahara
Takashi Horiyama
Shin-ichi Minato
Publisher: Springer International Publishing
Book: WALCOM: Algorithms and Computation
Print ISBN: 978-3-030-39880-4

Electronic ISBN: 978-3-030-39881-1

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39881-1_18

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner