{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiduy4exobdcbigwbmix67c7m7xyb3jzlku7zerwz632p3euaud6uu",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mjiw22eq2qa2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.10828v1",
  "publishedAt": "2026-04-14T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Anastasiia Tkachenko",
    "Haitao Wang"
  ],
  "textContent": "**Authors:** Anastasiia Tkachenko, Haitao Wang\n\nFor a set $\\mathcal{D}$ of disks in the plane, its disk graph $G(\\mathcal{D})$ is the graph with vertex set $\\mathcal{D}$, where two vertices are adjacent if and only if the corresponding disks intersect. Given a set $\\mathcal{D}$ of $n$ weighted disks, computing a maximum independent set of $G(\\mathcal{D})$ is NP-hard. In this paper, we present an $O(n^3\\log n)$-time algorithm for this problem in a special setting in which the disks are in convex position, meaning that every disk appears on the convex hull of $\\mathcal{D}$. This setting has been studied previously for disks of equal radius, for which an $O(n^{37/11})$-time algorithm was known. Our algorithm also works in the weighted case where disks have weights and the goal is to compute a maximum-weight independent set. As an application of our result, we obtain an $O(n^3\\log^2 n)$-time algorithm for the dispersion problem on a set of $n$ disks in convex position: given an integer $k$, compute a subset of $k$ disks that maximizes the minimum pairwise distance among all disks in the subset.",
  "title": "Maximum Independent Sets in Disk Graphs with Disks in Convex Position"
}