skip to main content
10.5555/1109557.1109649acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Max-tolerance graphs as intersection graphs: cliques, cycles, and recognition

Published: 22 January 2006 Publication History

Abstract

Max-tolerance graphs can be regarded as generalized interval graphs, where two intervals Ii and Ij only induce an edge in the corresponding graph iff they overlap for an amount of at least max{ti, tj} where ti is an individual tolerance parameter associated to each interval Ii. A new geometric characterization of max-tolerance graphs as intersection graphs of isosceles right triangles, shortly called semi-squares, leverages the solution of various graph-theoretic problems in connection with max-tolerance graphs. First, we solve the maximal and maximum cliques problem. It arises naturally in DNA sequence analysis where the maximal cliques might be interpreted as functional domains carrying biologically meaningful information. We prove an upper bound of O(n3) for the number of maximal cliques in max-tolerance graphs and give an efficient O(n3) algorithm for their computation. In the same vein, the semi-square representation yields a simple proof for the fact that this bound is asymptotically tight, i.e., a class of max-tolerance graphs is presented where the instances have Ω(n3) maximal cliques. Additionally, we answer an open question posed in [8] by showing that max-tolerance graphs do not contain complements of cycles Cn for n > 9. By exploiting the new representation more deeply, we can go even further and prove that the recognition problem for max-tolerance graphs is NP-hard.

References

[1]
S. F. Altschul, W. Gish, W. Miller, E. W. Myers and D. J. Lipman. Basic local alignment search tool. J. Mol. Biol., 215, pp. 403--410, 1990. http://www.ncbi.nlm.nih.gov/BLAST/
[2]
K. S. Booth and G. S. Lueker. Testing for the consecutive ones property, interval graphs, and planarity using PQ-tree algorithms. J. Comput. Sys. Sci., 13, pp. 335--379, 1976.
[3]
K. Bogart, G. Isaak, J. Laison, and A. Trenk. Comparability invariance results for tolerance orders. Order, 18, pp. 281--294, 2001.
[4]
P. C. Fishburn, Interval Orders and Interval Graphs: A Study of Partially Ordered Sets, John Wiley & Sons, New York, 1985.
[5]
D. R. Fulkerson and O. A. Gross. Incidence matrices and interval graphs. Pacific J. Math., 15, pp. 835--855, 1965.
[6]
M. Garey and D. Johnson. Computers and Intractability - A Guide to the Theory of NP-Completeness, Freeman, 1979
[7]
M. C. Golumbic. Algorithmic graph theory and perfect graphs. Annals of Discrete Mathematics, 57, 2004.
[8]
M. C. Golumbic, A. Trenk. Tolerance Graphs. Cambridge Studies in Advanced Mathematics 89, Cambridge University Press, 2004, 265 pp.
[9]
P. Hliněný, J. Kratochvíl. Representing graphs by disks and balls (a survey of recognition-complexity results) Discrete Math, 229 (2001), pp. 101--124.
[10]
M. S. Jacobson, F. R. Morris, E. R. Scheinermann. General results on tolerance intersection graphs. J. Graph Theory, 15, pp. 573--577, 1991.
[11]
J. Kratochvíl. Intersection graphs of noncrossing arc-connected sets in the plane. In: Graph Drawing (S. North ed.), Proceedings Graph Drawing '96, Berkeley, September 1996, Lecture Notes in Computer Science 1190, Springer Verlag, Berlin Heidelberg, 1997, pp. 257--270.
[12]
S. Skiena. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Addison-Wesley, pp. 163--164, 1990.

Cited By

View all
  • (2018)Planar graphs as l-intersection or l-contact graphsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175278(172-184)Online publication date: 7-Jan-2018
  • (2014)On Intersection Graphs of Convex PolygonsProceedings of the 16th International Workshop on Combinatorial Image Analysis - Volume 846610.1007/978-3-319-07148-0_4(25-36)Online publication date: 28-May-2014
  • (2011)An intersection model for multitolerance graphsProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133136(1306-1317)Online publication date: 23-Jan-2011
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
January 2006
1261 pages
ISBN:0898716055

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 2006

Check for updates

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2018)Planar graphs as l-intersection or l-contact graphsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175278(172-184)Online publication date: 7-Jan-2018
  • (2014)On Intersection Graphs of Convex PolygonsProceedings of the 16th International Workshop on Combinatorial Image Analysis - Volume 846610.1007/978-3-319-07148-0_4(25-36)Online publication date: 28-May-2014
  • (2011)An intersection model for multitolerance graphsProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133136(1306-1317)Online publication date: 23-Jan-2011
  • (2011)Integer representations of convex polygon intersection graphsProceedings of the twenty-seventh annual symposium on Computational geometry10.1145/1998196.1998248(300-307)Online publication date: 13-Jun-2011
  • (2010)Convex polygon intersection graphsProceedings of the 18th international conference on Graph drawing10.5555/1964371.1964407(377-388)Online publication date: 21-Sep-2010
  • (2010)Triangle contact representations and dualityProceedings of the 18th international conference on Graph drawing10.5555/1964371.1964396(262-273)Online publication date: 21-Sep-2010

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media