×

Max point-tolerance graphs. (English) Zbl 1350.05118

Summary: A graph \(G\) is a max point-tolerance (MPT) graph if each vertex \(v\) of \(G\) can be mapped to a pointed-interval \((I_v, p_v)\) where \(I_v\) is an interval of \(\mathbb{R}\) and \(p_v \in I_v\) such that \(u v\) is an edge of \(G\) iff \(I_u \cap I_v \supseteq \{p_u, p_v \}\). MPT graphs model relationships among DNA fragments in genome-wide association studies as well as basic transmission problems in telecommunications. We formally introduce this graph class, characterize it, study combinatorial optimization problems on it, and relate it to several well known graph classes. We characterize MPT graphs as a special case of several 2D geometric intersection graphs; namely, triangle, rectangle, L-shape, and line segment intersection graphs. We further characterize MPT as having certain linear orders on their vertex set. Our last characterization is that MPT graphs are precisely obtained by intersecting special pairs of interval graphs. We also show that, on MPT graphs, the maximum weight independent set problem can be solved in polynomial time, the coloring problem is NP-complete, and the clique cover problem has a 2-approximation. Finally, we demonstrate several connections to known graph classes; e.g., MPT graphs strictly contain interval graphs and outerplanar graphs, but are incomparable to permutation, chordal, and planar graphs.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
05C22 Signed and weighted graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Asinowski, A.; Cohen, E.; Golumbic, M. C.; Limouzy, V.; Lipshteyn, M.; Stern, M., Vertex intersection graphs of paths on a grid, J. Graph Algorithms Appl., 16, 129-150 (2012) · Zbl 1254.68184
[2] Booth, K. S.; Lueker, G. S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. System Sci., 13, 335-379 (1976) · Zbl 0367.68034
[3] Catanzaro, D.; Labbé, M.; Halldórsson, B. V., An integer programming formulation of the parsimonious loss of heterozigosity problem, IEEE Trans. Comput. Biol. Bioinform., 10, 6, 1391-1402 (2013)
[4] Chalermsook, P., Coloring and maximum independent set of rectangles, (Goldberg, L.; Jansen, K.; Ravi, R.; Rolim, J., Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Lecture Notes in Computer Science, vol. 6845 (2011)), 123-134 · Zbl 1343.90076
[5] Chaplick, S.; Kobourov, S.; Ueckerdt, T., Equilateral L-contact graphs, (Brandstädt, A.; Jansen, K.; Reischuk, R., Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 8165 (2013)), 139-151 · Zbl 1400.05235
[6] Chaplick, S.; Ueckerdt, T., Planar graphs as VPG-graphs, (Didimo, W.; Patrignani, M., Graph Drawing. Graph Drawing, Lecture Notes in Computer Science, vol. 7704 (2013)), 174-186 · Zbl 1377.05121
[7] Chepoi, V.; Felsner, S., Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve, Comput. Geom., Theory Appl., 46, 9, 1036-1041 (2013) · Zbl 1270.05028
[9] Correa, J.; Feuilloley, L.; Soto, J., Independent and hitting sets of rectangles intersecting a diagonal line, (LATIN 2014: Theoretical Informatics. LATIN 2014: Theoretical Informatics, Lecture Notes in Computer Science, vol. 8392 (2014)), 35-46 · Zbl 1407.68505
[10] de Fraysseix, H.; de Mendez, P. O.; Rosenstiehl, P., On triangle contact graphs, Combin. Probab. Comput., 3, 233-246 (1994) · Zbl 0807.05028
[11] Dion, G.; Jost, V.; Queyranne, M., Clique partitioning of interval graphs with submodular costs on the cliques, RAIRO Oper. Res., 41, 275-287 (2007) · Zbl 1213.90214
[12] Dirac, G., On rigid circuit graphs, Abh. Math. Semin. Univ. Hambg., 25, 71-76 (1961) · Zbl 0098.14703
[13] Ehrlich, G.; Even, S.; Tarjan, R., Intersection graphs of curves in the plane, J. Combin. Theory Ser. B, 21, 1, 8-20 (1976) · Zbl 0348.05113
[14] Felsner, S., Geometric Graphs and Arrangements (2004), Vieweg Wiesbaden · Zbl 1051.05036
[15] Fishburn, P., Interval Orders and Interval Graphs: A Study of Partially Ordered Sets (1985), John Wiley & Sons: John Wiley & Sons New York, NY, USA · Zbl 0551.06001
[16] Fowler, R. J.; Paterson, M.; Tanimoto, S. L., Optimal packing and covering in the plane are NP-complete, Inform. Process. Lett., 12, 133-137 (1981) · Zbl 0469.68053
[18] Fulkerson, D. R.; Gross, O. A., Incidence matrices and interval graphs, Pacific J. Math, 15, 835-855 (1965) · Zbl 0132.21001
[19] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman & Co.: W. H. Freeman & Co. New York, NY, USA · Zbl 0411.68039
[20] Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. H., The complexity of coloring circular arcs and chords, SIAM J. Algebr. Discrete Methods, 1, 216-227 (1980) · Zbl 0499.05058
[21] Gavril, F., A recognition algorithm for the intersection graphs of paths in trees, Discrete Math., 23, 211-227 (1978) · Zbl 0398.05060
[22] Golumbic, M. C., (Algorithmic Graph Theory and Perfect Graphs. Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, vol. 57 (2004), Elsevier) · Zbl 1050.05002
[24] Golumbic, M. C.; Trenk, A., (Tolerance Graphs. Tolerance Graphs, Cambridge Studies in Advanced Mathematics, vol. 89 (2004), Cambridge University Press) · Zbl 1091.05001
[25] Halldórsson, B. V.; Aguiar, D.; Tarpine, R.; Istrail, S., The Clark phaseable sample size problem: Long-range phasing and loss of heterozygosity in GWAS, J. Comput. Biol., 18, 323-333 (2011)
[26] Hixon, T., Hook graphs and more: Some contributions to geometric graph theory (2013), Institut für Mathematik, Technische Universität: Institut für Mathematik, Technische Universität Berlin, (Master’s thesis)
[27] Hsu, W.-L.; Tsai, K.-H., Linear time algorithms on circular-arc graphs, Inform. Process. Lett., 40, 123-129 (1991) · Zbl 0748.68044
[28] Imai, H.; Asano, T., Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane, J. Algorithms, 4, 310-323 (1983) · Zbl 0548.68067
[29] Jeon, W. S.; Jeong, D. G., Call admission control for mobile multimedia communications with traffic asymmetry between uplink and downlink, IEEE Trans. Veh. Technol., 50, 1, 59-66 (2001)
[31] Keil, J. M.; Stewart, L., Approximating the minimum clique cover and other hard problems in subtree filament graphs, Discrete Appl. Math., 14, 1983-1995 (2006) · Zbl 1110.68103
[33] Kostochka, A.; Nešetřil, J., Coloring relatives of intervals on the plane, I: Chromatic number versus girth, European J. Combin., 19, 103-110 (1998) · Zbl 0886.05064
[34] Kratochvíl, J.; Nešetřil, J., Independent set and clique problems in intersection-defined classes of graphs, Comment. Math. Univ. Carolin., 31, 85-93 (1990) · Zbl 0727.05056
[35] Kratsch, D.; Stewart, L., Domination on cocomparability graphs, SIAM J. Discrete Math., 6, 400-417 (1993) · Zbl 0780.05032
[36] Lekkerkerker, C. G.; Boland, J. C., Representation of a finite graph by a set of intervals on the real line, Fund. Math., 51, 45-64 (1962) · Zbl 0105.17501
[37] Lubiw, A., A weighted min-max relation for intervals, J. Combin. Theory Ser. B, 53, 151-172 (1991) · Zbl 0758.05003
[38] Maehara, H., A digraph represented by a family of boxes or spheres, J. Graph Theory, 8, 431-439 (1984) · Zbl 0552.05030
[39] McConnell, R. M., Linear-time recognition of circular-arc graphs, Algorithmica, 37, 93-147 (2003) · Zbl 1060.68088
[40] Mitchell, S. L., Linear algorithms to recognize outerplanar and maximal outerplanar graphs, Inform. Process. Lett., 9, 5, 229-232 (1979) · Zbl 0444.68055
[41] Olariu, S., An optimal greedy heuristic to color interval graphs, Inform. Process. Lett., 37, 65-80 (1991)
[42] Prisner, E., A characterization of interval catch digraphs, Discrete Math., 73, 285-289 (1989) · Zbl 0669.05038
[43] Prisner, E., Algorithms for interval catch digraphs, Discrete Appl. Math., 51, 147-157 (1994) · Zbl 0810.68104
[44] Proskurowski, A.; Syslo, M., Efficient vertex- and edge-coloring of outerplanar graphs, SIAM J. Algebr. Discrete Methods7, 1, 131-136 (1986) · Zbl 0582.05026
[45] Quest, M.; Wegner, G., Characterizations of the graphs with boxicity \(\leq 2\), Discrete Math., 81, 187-192 (1990) · Zbl 0725.05070
[46] Ramalingam, G.; Rangan, C. P., A uniform approach to domination problems on interval graphs, Inform. Process. Lett., 27, 271-274 (1988) · Zbl 0658.05040
[47] Raychaudhuri, A., On powers of interval and unit interval graphs, Congr. Numer., 59, 235-242 (1987) · Zbl 0642.05051
[48] Roberts, F., Representations of indifference relations (1968), Stanford University, (Ph.D. thesis)
[50] Shrestha, A. M.S.; Tayu, S.; Ueno, S., On orthogonal ray graphs, Discrete Appl. Math., 158, 1650-1659 (2010) · Zbl 1222.05219
[52] Stefansson, H.; Rujescu, D.; Cichon, S.; Pietiläinen, O. P.H.; Ingason, A.; Steinberg, S.; Fossdal, R.; Sigurdsson, E.; Sigmundsson, T.; Buizer-Voskamp, J. E.; Hansen, T.; Jakobsen, K. D.; Muglia, P.; Francks, C.; Matthews, P. M.; Gylfason, A.; Halldorsson, B. V.; Gudbjartsson, D.; Thorgeirsson, T. E.; Sigurdsson, A.; Jonasdottir, A.; Jonasdottir, A.; Bjornsson, A.; Mattiasdottir, S.; Blondal, T.; Haraldsson, M.; Magnusdottir, B. B.; Giegling, I.; Moeller, H. J.; Hartmann, A.; Shianna, K. V.; Ge, D.; Need, A. C.; Crombie, C.; Fraser, G.; Walker, N.; Lonnqvist, J.; Suvisaari, J.; Tuulio-Henriksson, A.; Paunio, T.; Toulopoulou, T.; Bramon, E.; Forti, M. D.; Murray, R.; Ruggeri, M.; Vassos, E.; Tosato, S.; Walshe, M.; Li, T.; Vasilescu, C.; Moehleisen, T. W.; Wang, A. G.; Ullum, H.; Djurovic, S.; Melle, I.; Olesen, J.; Kiemeney, L. A.; Franke, B.; Sabatti, C.; Freimer, N. B.; Gulcher, J. R.; Thorsteinsdottir, U.; Kong, A.; Andreassen, O. A.; Ophoff, R. A.; Georgi, A.; Rietschel, M.; Werge, T.; Petursson, H.; Goldstein, D. B.; Nöthen, M. M.; Peltonen, L.; Collier, D. A.; Clair, D. S.; Stefansson, K., Large recurrent microdeletions associated with schizophrenia, Nature, 455, 232-236 (2008)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.