On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid

DOI10.1016/j.dam.2023.01.010OpenAlexW4318768319MaRDI QIDQ2691570

Elisabeth Gaar, Eranda Çela

Publication date: 29 March 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2002.05998

zbMATH Keywords

complete bipartite graphEPG graphpaths on a grid(monotonic) bend number

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• Edge intersection graphs of \(L\)-shaped paths in grids
• VPG and EPG bend-numbers of Halin graphs
• On the bend-number of planar and outerplanar graphs
• Clique coloring \(B_1\)-EPG graphs
• The edge intersection graphs of paths in a tree
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends
• Edge and vertex intersection of paths in a tree
• Computing maximum cliques in \(B_2\)-EPG graphs
• On split \(B_1\)-EPG graphs
• Edge-intersection graphs of grid paths: the bend-number
• On Independent Set on B1-EPG Graphs
• Approximation Algorithms for B 1-EPG Graphs
• Edge intersection graphs of single bend paths on a grid
• Vertex Intersection Graphs of Paths on a Grid
• On Edge Intersection Graphs of Paths with 2 Bends
• EPG-representations with Small Grid-Size
• Edge-Intersection Graphs of k-Bend Paths in Grids
• Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid