The Induced Separation Dimension of a Graph
| العنوان: | The Induced Separation Dimension of a Graph |
|---|---|
| المؤلفون: | Rogers Mathew, Emile Ziedan, Martin Charles Golumbic, Jérémie Dusart, Deepak Rajendraprasad |
| المصدر: | Algorithmica. 80:2834-2848 |
| بيانات النشر: | Springer Science and Business Media LLC, 2017. |
| سنة النشر: | 2017 |
| مصطلحات موضوعية: | Discrete mathematics, General Computer Science, Applied Mathematics, 010102 general mathematics, Dimension (graph theory), 0102 computer and information sciences, Disjoint sets, 01 natural sciences, Linear ordering, Computer Science Applications, Combinatorics, Line segment, 010201 computation theory & mathematics, Chordal graph, Theory of computation, Acyclic orientation, 0101 mathematics, Time complexity, Mathematics |
| الوصف: | A linear ordering of the vertices of a graph G separates two edges of G if both the endpoints of one precede both the endpoints of the other in the order. We call two edges $$\{a,b\}$$ and $$\{c,d\}$$ of G strongly independent if the set of endpoints $$\{a,b,c,d\}$$ induces a $$2K_2$$ in G. The induced separation dimension of a graph G is the smallest cardinality of a family $$\mathcal {L}$$ of linear orders of V(G) such that every pair of strongly independent edges in G are separated in at least one of the linear orders in $$\mathcal {L}$$ . For each $$k \in \mathbb {N}$$ , the family of graphs with induced separation dimension at most k is denoted by $${\text {ISD}}(k)$$ . In this article, we initiate a study of this new dimensional parameter. The class $${\text {ISD}}(1)$$ or, equivalently, the family of graphs which can be embedded on a line so that every pair of strongly independent edges are disjoint line segments, is already an interesting case. On the positive side, we give characterizations for chordal graphs in $${\text {ISD}}(1)$$ which immediately lead to a polynomial time algorithm which determines the induced separation dimension of chordal graphs. On the negative side, we show that the recognition problem for $${\text {ISD}}(1)$$ is NP-complete for general graphs. Nevertheless, we show that the maximum induced matching problem can be solved efficiently in $${\text {ISD}}(1)$$ . We then briefly study $${\text {ISD}}(2)$$ and show that it contains many important graph classes like outerplanar graphs, chordal graphs, circular arc graphs and polygon-circle graphs. Finally, we describe two techniques to construct graphs with large induced separation dimension. The first one is used to show that the maximum induced separation dimension of a graph on n vertices is $$\Theta (\lg n)$$ and the second one is used to construct AT-free graphs with arbitrarily large induced separation dimension. The second construction is also used to show that, for every $$k \ge 2$$ , the recognition problem for $${\text {ISD}}(k)$$ is NP-complete even on AT-free graphs. |
| تدمد: | 1432-0541 0178-4617 |
| DOI: | 10.1007/s00453-017-0353-x |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::1a2c5ca5caa0d2e6c32f0f6d639d6252 https://doi.org/10.1007/s00453-017-0353-x |
| Rights: | CLOSED |
| رقم الانضمام: | edsair.doi...........1a2c5ca5caa0d2e6c32f0f6d639d6252 |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 14320541 01784617 |
|---|---|
| DOI: | 10.1007/s00453-017-0353-x |