B1-EPG representations using block-cutpoint trees
DOI:
https://doi.org/10.5540/03.2021.008.01.0379Palavras-chave:
Edge intersection graph, Block-cutpoint trees, Block graphs, Cactus graphsResumo
In this paper, we are interested in the edge intersection graphs of paths of a grid whereeach path has at most one bend, called B1-EPG graphs and first introduced by Golumbic et al(2009). We also consider a proper subclass of B1-EPG, thex-EPG graphs, which allows paths onlyin “x” shape. We show that two superclasses of trees are B1-EPG (one of them being the cactusgraphs). On the other hand, we show that the block graphs arex-EPG and provide a linear timealgorithm to producex-EPG representations of generalization of trees. These proofs employed anew technique from previous results in the area based on block-cutpoint trees of the respectivegraphs.Downloads
Referências
Asinowski, A., Ries, B. Some properties of edge intersection graphs of single-bend paths on agrid.Discrete Mathematics, 312(2):427-440, 2012. DOI: 10.1016/j.disc.2011.10.005.
Biedl, T. and Stern, M. On edge-intersection graphs of k-bend paths in grids,Discrete Mathe-matics & Theoretical Computer Science, 12(1):1-12, 2010. DOI: 10.1007/978-3-642-02882-310.
Booth, K. S. and Lueker, G. S., Testing for the consecutive ones property, interval graphs,and graph planarity using PQ-tree algorithms.Journal of Computer and System Sciences,13:335-379, 1976. DOI: 10.1016/S0022-0000(76)80045-1.
Brady, M. L. and Sarrafzadeh, M. Stretching a knock-knee layout for multilayer wiring,IEEETransactions on Computers, 39:148-151, 1990. DOI: 10.1109/12.46293.
Cela, E. and Gaar, E. Monotonic Representations of Outerplanar Graphs as Edge IntersectionGraphs of Paths on a Grid.arXiv preprint arXiv:1908.01981, 2019.
Golumbic, M. C., Lipshteyn, M. and Stern, M. Edge intersection graphs of single bend pathson a grid,Networks: An International Journal, 54(3):130–138, 2009. DOI: 10.1002/net.20305.
Harary, F.Graph Theory, Addison-Wesley, Massachusetts, 1969.[8] Heldt, D., Knauer, K. and Ueckerdt, T. Edge-intersection graphs of grid paths: the bend-number,Discrete Applied Mathematics, 167:144-162, 2014. DOI: 10.1016/j.dam.2013.10.035.[9] Heldt, D., Knauer, K. and Ueckerdt, T. On the bend-number of planar and outerplanar graphs,Discrete Applied Mathematics, 179:109-119, 2014. DOI: 10.1016/j.dam.2014.07.015.
Martin Pergel, P. R. On edge intersection graphs of paths with 2 bends,Discrete AppliedMathematics, 226:106-116, 2017. DOI: 10.1007/978-3-662-53536-318.
