nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Intersection Graphs of Non-crossing Paths

verfasst von : Steven Chaplick

Erschienen in: Graph-Theoretic Concepts in Computer Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We study graph classes modeled by families of non-crossing (NC) connected sets. Two classic graph classes in this context are disk graphs and proper interval graphs. We focus on the cases when the sets are paths and the host is a tree. Forbidden induced subgraph characterizations and linear time certifying recognition algorithms are given for intersection graphs of NC paths of a tree (and related subclasses). For intersection graphs of NC paths of a tree, the dominating set problem is shown to be solvable in linear time. Also, each such graph is shown to have a Hamiltonian cycle if and only if it is 2-connected, and to have a Hamiltonian path if and only if its block-cutpoint tree is a path.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Counting Independent Sets in Graphs with Bounded Bipartite Pathwidth

Nächstes Kapitel Reconfiguring Hamiltonian Cycles in L-Shaped Grid Graphs

Note: all \(\exists \mathbb {R}\)-hard problems are NP-hard, see [28] for an introduction to \(\exists \mathbb {R}\).

Usually defined as having no interval strictly contained within any other.

A graph is a split graph when its vertices can be partitioned into a clique and an independent set. It is easy to see that split graphs are chordal.

Bertossi, A.A.: Finding Hamiltonian circuits in proper interval graphs. Inf. Process. Lett. 17(2), 97–101 (1983). https://doi.org/10.1016/0020-0190(83)90078-9MathSciNetCrossRefMATH

Booth, K.S., Johnson, J.H.: Dominating sets in chordal graphs. SIAM J. Comput. 11(1), 191–199 (1982). https://doi.org/10.1137/0211015MathSciNetCrossRefMATH

Chaplick, S.: Intersection graphs of non-crossing paths. CoRR abs/1907.00272 (2019)

Chaplick, S., Fomin, F.V., Golovach, P.A., Knop, D., Zeman, P.: Kernelization of graph hamiltonicity: proper H-graphs. In: Friggstad, Z., Sack, J.-R., Salavatipour, M.R. (eds.) WADS 2019. LNCS, vol. 11646, pp. 296–310. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-24766-9_22CrossRef

Chaplick, S., Gutierrez, M., Lévêque, B., Tondato, S.B.: From path graphs to directed path graphs. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol. 6410, pp. 256–265. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16926-7_24CrossRef

Chaplick, S., Töpfer, M., Voborník, J., Zeman, P.: On H-topological intersection graphs. In: Bodlaender, H.L., Woeginger, G.J. (eds.) WG 2017. LNCS, vol. 10520, pp. 167–179. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68705-6_13CrossRef

Chaplick, S., Zeman, P.: Combinatorial problems on H-graphs. In: EUROCOMB, vol. 61, pp. 223–229 (2017). https://doi.org/10.1016/j.endm.2017.06.042CrossRef

Corneil, D.G., Olariu, S., Stewart, L.: The LBFS structure and recognition of interval graphs. SIAM J. Discrete Math. 23(4), 1905–1953 (2009). https://doi.org/10.1137/S0895480100373455MathSciNetCrossRefMATH

Corneil, D.G., Perl, Y.: Clustering and domination in perfect graphs. Discrete Appl. Math. 9(1), 27–39 (1984). https://doi.org/10.1016/0166-218X(84)90088-XMathSciNetCrossRefMATH

10.

Deng, X., Hell, P., Huang, J.: Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs. SIAM J. Comput. 25(2), 390–403 (1996). https://doi.org/10.1137/S0097539792269095MathSciNetCrossRefMATH

11.

Dietz, P.F.: Intersection graph algorithms. Ph.D. thesis, Cornell University (1984)

12.

Farber, M.: Independent domination in chordal graphs. Oper. Res. Lett. 1(4), 134–138 (1982). https://doi.org/10.1016/0167-6377(82)90015-3MathSciNetCrossRefMATH

13.

Fomin, F.V., Golovach, P.A., Raymond, J.: On the tractability of optimization problems on H-graphs. In: ESA. LIPIcs, vol. 112, pp. 30:1–30:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018). https://doi.org/10.4230/LIPIcs.ESA.2018.30

14.

Fulkerson, D., Gross, O.: Incidence matrices and interval graphs. Pac. J. Math. 15, 835–855 (1965)MathSciNetCrossRef

15.

Galinier, P., Habib, M., Paul, C.: Chordal graphs and their clique graphs. In: Nagl, M. (ed.) WG 1995. LNCS, vol. 1017, pp. 358–371. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60618-1_88CrossRef

16.

Gavril, F.: The intersection graphs of subtrees of trees are exactly the chordal graphs. J. Comb. Theory Ser. B 16, 47–56 (1974)MathSciNetCrossRef

17.

Gavril, F.: A recognition algorithm for the intersection graphs of directed paths in directed trees. Discrete Math. 13(3), 237–249 (1975). https://doi.org/10.1016/0012-365X(75)90021-7MathSciNetCrossRefMATH

18.

Gavril, F.: A recognition algorithm for the intersection of graphs of paths in trees. Discrete Math. 23, 211–227 (1978)MathSciNetCrossRef

19.

Gavril, F.: Intersection graphs of helly families of subtrees. Discrete Appl. Math. 66, 45–56 (1996)MathSciNetCrossRef

20.

Golumbic, M.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics. Elsevier, Amsterdam (2004)MATH

21.

Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372–378 (1973). https://doi.org/10.1145/362248.362272CrossRef

22.

Kang, R.J., Müller, T.: Sphere and dot product representations of graphs. Discrete Comput. Geom. 47(3), 548–568 (2012)MathSciNetCrossRef

23.

Kratochvíl, J.: Intersection graphs of noncrossing arc-connected sets in the plane. In: North, S. (ed.) GD 1996. LNCS, vol. 1190, pp. 257–270. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-62495-3_53CrossRef

24.

Kumar, P., Madhavan, C.: Clique tree generalization and new subclasses of chordal graphs. Discrete Appl. Math. 117(1–3), 109–131 (2002). https://doi.org/10.1016/S0166-218X(00)00336-XMathSciNetCrossRefMATH

25.

Lai, T., Wei, S.: The edge hamiltonian path problem is NP-complete for bipartite graphs. Inf. Process. Lett. 46(1), 21–26 (1993). https://doi.org/10.1016/0020-0190(93)90191-BMathSciNetCrossRefMATH

26.

Lekkerkerker, C., Boland, J.: Representation of a finite graph by a set of intervals on a real line. Fundam. Math. 51(1), 45–64 (1962)MathSciNetCrossRef

27.

Lèvêque, B., Maffray, F., Preissmann, M.: Characterizing path graphs by forbidden induced subgraphs. J. Graph Theory 62, 4 (2009)MathSciNetCrossRef

28.

Matousek, J.: Intersection graphs of segments and \(\exists \mathbb{R}\). CoRR abs/1406.2636 (2014). http://arxiv.org/abs/1406.2636

29.

McKee, T., McMorris, F.: Intersection Graph Theory. SIAM (1999)

30.

Monma, C.L., Wei, V.K.: Intersection graphs of paths in a tree. J. Comb. Theory Ser. B 41(2), 141–181 (1986)MathSciNetCrossRef

31.

Müller, H.: Hamiltonian circuits in chordal bipartite graphs. Discrete Math. 156(1–3), 291–298 (1996). https://doi.org/10.1016/0012-365X(95)00057-4MathSciNetCrossRefMATH

32.

Narasimhan, G.: A note on the hamiltonian circuit problem on directed path graphs. Inf. Process. Lett. 32(4), 167–170 (1989). https://doi.org/10.1016/0020-0190(89)90038-0MathSciNetCrossRefMATH

33.

Panda, B.S.: The forbidden subgraph characterization of directed vertex graphs. Discrete Math. 196(1–3), 239–256 (1999). https://doi.org/10.1016/S0012-365X(98)00127-7MathSciNetCrossRefMATH

34.

Roberts, F.S.: On nontransitive indifference. J. Math. Psychol. 7(2), 243–258 (1970). https://doi.org/10.1016/0022-2496(70)90047-7MathSciNetCrossRefMATH

35.

Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266–283 (1976). https://doi.org/10.1137/0205021MathSciNetCrossRefMATH

36.

Schäffer, A.A.: A faster algorithm to recognize undirected path graphs. Discrete Appl. Math. 43, 261–295 (1993). https://doi.org/10.1016/0166-218X(93)90116-6MathSciNetCrossRefMATH

37.

Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38(3), 364–372 (1980)MathSciNetCrossRef

Titel: Intersection Graphs of Non-crossing Paths
verfasst von: Steven Chaplick
Verlag: Springer International Publishing
Buch: Graph-Theoretic Concepts in Computer Science
Print ISBN: 978-3-030-30785-1

Electronic ISBN: 978-3-030-30786-8

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-30786-8_24

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"