DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2023.30

Finding a Maximum Clique in a Disk Graph

Authors: Jared Espenant, J. Mark Keil, and Debajyoti Mondal

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract

A disk graph is an intersection graph of disks in the Euclidean plane, where the disks correspond to the vertices of the graph and a pair of vertices are adjacent if and only if their corresponding disks intersect. The problem of determining the time complexity of computing a maximum clique in a disk graph is a long-standing open question that has been very well studied in the literature. The problem is known to be open even when the radii of all the disks are in the interval [1,(1+ε)], where ε > 0. If all the disks are unit disks then there exists an O(n³log n)-time algorithm to compute a maximum clique, which is the best-known running time for over a decade. Although the problem of computing a maximum clique in a disk graph remains open, it is known to be APX-hard for the intersection graphs of many other convex objects such as intersection graphs of ellipses, triangles, and a combination of unit disks and axis-parallel rectangles. Here we obtain the following results. - We give an algorithm to compute a maximum clique in a unit disk graph in O(n^2.5 log n)-time, which improves the previously best known running time of O(n³log n) [Eppstein '09]. - We extend a widely used "co-2-subdivision approach" to prove that computing a maximum clique in a combination of unit disks and axis-parallel rectangles is NP-hard to approximate within 4448/4449 ≈ 0.9997. The use of a "co-2-subdivision approach" was previously thought to be unlikely in this setting [Bonnet et al. '20]. Our result improves the previously known inapproximability factor of 7633010347/7633010348 ≈ 0.9999. - We show that the parameter minimum lens width of the disk arrangement may be used to make progress in the case when disk radii are in [1,(1+ε)]. For example, if the minimum lens width is at least 0.265 and ε ≤ 0.0001, which still allows for non-Helly triples in the arrangement, then one can find a maximum clique in polynomial time.

Cite as

Jared Espenant, J. Mark Keil, and Debajyoti Mondal. Finding a Maximum Clique in a Disk Graph. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{espenant_et_al:LIPIcs.SoCG.2023.30,
  author =	{Espenant, Jared and Keil, J. Mark and Mondal, Debajyoti},
  title =	{{Finding a Maximum Clique in a Disk Graph}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.30},
  URN =		{urn:nbn:de:0030-drops-178803},
  doi =		{10.4230/LIPIcs.SoCG.2023.30},
  annote =	{Keywords: Maximum clique, Disk graph, Time complexity, APX-hardness}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2018.12

Boundary Labeling for Rectangular Diagrams

Authors: Prosenjit Bose, Paz Carmi, J. Mark Keil, Saeed Mehrabi, and Debajyoti Mondal

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract

Given a set of n points (sites) inside a rectangle R and n points (label locations or ports) on its boundary, a boundary labeling problem seeks ways of connecting every site to a distinct port while achieving different labeling aesthetics. We examine the scenario when the connecting lines (leaders) are drawn as axis-aligned polylines with few bends, every leader lies strictly inside R, no two leaders cross, and the sum of the lengths of all the leaders is minimized. In a k-sided boundary labeling problem, where 1 <= k <= 4, the label locations are located on the k consecutive sides of R. In this paper we develop an O(n^3 log n)-time algorithm for 2-sided boundary labeling, where the leaders are restricted to have one bend. This improves the previously best known O(n^8 log n)-time algorithm of Kindermann et al. (Algorithmica, 76(1):225-258, 2016). We show the problem is polynomial-time solvable in more general settings such as when the ports are located on more than two sides of R, in the presence of obstacles, and even when the objective is to minimize the total number of bends. Our results improve the previous algorithms on boundary labeling with obstacles, as well as provide the first polynomial-time algorithms for minimizing the total leader length and number of bends for 3- and 4-sided boundary labeling. These results settle a number of open questions on the boundary labeling problems (Wolff, Handbook of Graph Drawing, Chapter 23, Table 23.1, 2014).

Cite as

Prosenjit Bose, Paz Carmi, J. Mark Keil, Saeed Mehrabi, and Debajyoti Mondal. Boundary Labeling for Rectangular Diagrams. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.SWAT.2018.12,
  author =	{Bose, Prosenjit and Carmi, Paz and Keil, J. Mark and Mehrabi, Saeed and Mondal, Debajyoti},
  title =	{{Boundary Labeling for Rectangular Diagrams}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.12},
  URN =		{urn:nbn:de:0030-drops-88386},
  doi =		{10.4230/LIPIcs.SWAT.2018.12},
  annote =	{Keywords: Boundary labeling, Dynamic programming, Outerstring graphs}
}

Search Results

Documents authored by Keil, J. Mark

Finding a Maximum Clique in a Disk Graph

Abstract

Cite as

Boundary Labeling for Rectangular Diagrams

Abstract

Cite as

Thanks for your feedback!

Could not send message