%0 Conference Paper %1 10.1007/978-3-030-30786-8_24 %A Chaplick, Steven %B Graph-Theoretic Concepts in Computer Science %C Cham %D 2019 %E Sau, Ignasi %E Thilikos, Dimitrios M. %I Springer International Publishing %K conference myown publication %P 311--324 %R 10.1007/978-3-030-30786-8_24 %T Intersection Graphs of Non-crossing Paths %U https://link.springer.com/chapter/10.1007%2F978-3-030-30786-8_24 %X 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. %@ 978-3-030-30786-8

@inproceedings{10.1007/978-3-030-30786-8_24, 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.}, added-at = {2019-10-02T11:24:51.000+0200}, address = {Cham}, author = {Chaplick, Steven}, biburl = {https://www.bibsonomy.org/bibtex/291e6b8ff1458d1aab651cd584ca32d10/chaplick}, booktitle = {Graph-Theoretic Concepts in Computer Science}, description = {Intersection Graphs of Non-crossing Paths}, doi = {10.1007/978-3-030-30786-8_24}, editor = {Sau, Ignasi and Thilikos, Dimitrios M.}, interhash = {0b0193132a65582e806843ceb32edf49}, intrahash = {91e6b8ff1458d1aab651cd584ca32d10}, isbn = {978-3-030-30786-8}, keywords = {conference myown publication}, pages = {311--324}, publisher = {Springer International Publishing}, timestamp = {2019-10-02T11:24:51.000+0200}, title = {Intersection Graphs of Non-crossing Paths}, url = {https://link.springer.com/chapter/10.1007%2F978-3-030-30786-8_24}, year = 2019 }