On edge intersection graphs of paths with 2 bends

DOI10.1016/J.DAM.2017.04.023MaRDI QIDQ2357780zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Martin Pergel, Paweł Rzążewski

Publication date 14 June 2017

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

Full work available at URL https://arxiv.org/abs/1711.05096, http://eprints.sztaki.hu/9063/

zbMATH Keywords

bend numberEPG-graphsrecognition

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: An EPG-representation of a graph $G$ is a collection of paths in a plane square grid, each corresponding to a single vertex of $G$, so that two vertices are adjacent if and only if their corresponding paths share infinitely many points. In this paper we focus on graphs admitting EPG-representations by paths with at most 2 bends. We show hardness of the recognition problem for this class of graphs, along with some subclasses. We also initiate the study of graphs representable by unaligned polylines, and by polylines, whose every segment is parallel to one of prescribed slopes. We show hardness of recognition and explore the trade-off between the number of bends and the number of slopes.

Recommendations

• On edge intersection graphs of paths with 2 bends
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends
• scientific article; zbMATH DE number 7272507
• Edge intersection graphs of single bend paths on a grid
• Edge intersection graphs of \(L\)-shaped paths in grids

Cites work

• Approximation algorithms for \(B _{1}\)-EPG graphs
• Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
• Edge intersection graphs of \(L\)-shaped paths in grids
• Edge intersection graphs of single bend paths on a grid
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends
• Edge-intersection graphs of grid paths: the bend-number
• scientific article; zbMATH DE number 2084282 (Why is no real title available?)
• On edge intersection graphs of paths with 2 bends
• On edge-intersection graphs of k-bend paths in grids
• Scheduling Split Intervals
• Some properties of edge intersection graphs of single-bend paths on a grid
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The maximum clique problem in multiple interval graphs
• Unit disk graphs

Cited in

(10)

• Edge-intersection graphs of boundary-generated paths in a grid
• Hardness and approximation for L-EPG and \(B_1\)-EPG graphs
• On edge intersection graphs of paths with 2 bends
• The complexity of Helly-B₁ EPG graph recognition
• Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
• On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
• Geometric representations of graphs with low polygonal complexity
• Clique cover on L-EPG representations of graphs
• Total (restrained) domination in B_k-EPG graphs and B_k-VPG graphs
• CPG graphs: some structural and hardness results

This page was built for publication: On edge intersection graphs of paths with 2 bends

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2357780)