Pith. sign in

REVIEW 59 references

Point Set Embeddability with List Constraints

T0 review · reviewed 2026-07-31 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read List-constrained point-set embeddability is polynomial for connected graphs on convex points once an embedding is fixed, yet NP-hard for bi-labeled matchings and for paths on general points.

desk verdict Clean complexity map for list-constrained point-set embeddability that settles the GD’13 open question and draws a sharp convex-vs-general split. read the letter →

arxiv 2607.24182 v1 pith:6KECMFXL submitted 2026-07-27 cs.CG cs.CCcs.DS

Thomas Depian , Joseph Dorfer , Boris Klemz , Matthias Pfretzschner , Lena Schlipf This is my paper · ORCID
classification cs.CGcs.CCcs.DS
keywords pointsetembeddinglistconstraintsparameterizedalgorithmsNP-hardnessdynamicprogramminggraphdrawingcomputationalgeometryvertexcover
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies whether a graph can be drawn with straight-line edges and no crossings when each vertex may sit only on a short list of allowed points from a finite set. On points in convex position the answer is still NP-hard for the simplest graphs (matchings or height-2 trees) once every list has size at most two, but becomes polynomial-time solvable for any connected graph that already carries a combinatorial embedding and fixed-parameter tractable in maximum degree when the embedding is free. On arbitrary point sets the same problem is NP-hard already for bi-labeled paths and cycles, yet fixed-parameter tractable in the vertex-cover number for bi-labeled instances; three labels per vertex make even two stars hard. The same boundary appears in the natural optimization and partial-drawing-extension variants. The results give a nearly complete complexity map that separates the geometric setting from the combinatorial one and answers a concrete open question left by earlier work on bi-colored trees.

What carries the argument

A dynamic program on the block-cut tree that greedily computes shortest feasible intervals for successive child blocks (Claim 3.8 and the two cases of Theorem 3.2), relying on free interchangeability of the root cut-vertex outside each occupied interval.

What would settle it

An explicit convex instance whose shortest outerplanar realization places some earlier block non-greedily and thereby frees a strictly shorter total interval than the dynamic program reports.

Watch

Extended reading notes

Core claim

When the host point set is convex, connectivity plus a prescribed combinatorial embedding is enough to decide list-constrained straight-line embeddability in polynomial time, while dropping either condition immediately yields NP-hardness; on general point sets the same decision problem collapses to NP-hardness even for paths of maximum degree two.

Load-bearing premise

The claim that a purely greedy left-to-right placement of child blocks always yields a globally shortest feasible interval, with no beneficial non-greedy reordering inside a block.

Editorial extensions

If this is right

  • Binary trees on two-colored convex point sets are polynomial-time embeddable, settling the open question of Frati et al.
  • Any FPT algorithm for general point sets must exploit a parameter at least as strong as vertex cover once lists may have size three.
  • Maximizing the number of straight-line edges under bi-label constraints admits no PTAS even for graphs of vertex-cover number two.
  • Partial drawings become fixed-parameter tractable once both the number of free vertices and the surplus of unused points are bounded.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same block-cut dynamic program may extend, with only minor changes, to outerplanar graphs that are disconnected once the number of components is treated as an additional parameter.
  • Hardness for bi-labeled paths already rules out FPT algorithms under almost every classical structural parameter on general point sets, so future positive results must either restrict geometry further or move to approximation.
  • The APX-hardness reduction suggests that even constant-factor approximation of the maximum number of embeddable edges is unlikely unless the lists are of size one.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: self-contained reductions and dynamic programs with no fitted quantities or load-bearing self-citation chains

full rationale

This is a pure theory paper in parameterized algorithms and computational geometry. All negative results are many-one reductions from established complete problems (3SAT, Planar Monotone 3SAT, Grid Tiling, MAX-2SAT(3)); the constructions define gadgets whose admissible placements encode truth assignments by explicit geometric crossings, not by renaming an input quantity. All positive results are self-contained: the convex DP (Theorem 3.2 / Claim 3.8) defines table entries T[B,p] as the first feasible endpoint and proves optimal substructure by induction plus the free interchangeability of the root cut-vertex (Observation 3.7) and Property 1 forbidding straddling edges; the bi-labeled vertex-cover FPT (Theorem 4.4) branches on 2^k placements then builds an explicit 2SAT formula; the star algorithms reduce to bipartite matching. No parameter is fitted to data and later called a prediction; no uniqueness theorem is imported from overlapping authors to forbid alternatives; self-citations are ordinary background (e.g., the open question of Frati et al. that the FPT answers). The derivation chain does not reduce any claimed result to its own inputs by construction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

Pure discrete-algorithms paper. No empirical fits. Background rests on standard graph-theoretic and geometric facts (planarity, BC-trees, outerplanar uniqueness, 2-SAT, known W[1]-hardness of Grid Tiling, APX-hardness of MAX-2SAT(3)) plus the modeling choice that straight-line edges and finite point sets define the problem.

assumptions (5)
  • domain assumption A graph admits a straight-line planar drawing on a point set only if the induced geometric graph is crossing-free (definition of L-realization).
    Invoked throughout; standard in geometric graph theory.
  • standard math Outerplanar combinatorial embeddings of 2-connected graphs are unique up to reflection (Corollary 3.5).
    Used to limit the embedding enumeration inside ALG2 to a factor of 2.
  • standard math Block-cut trees can be computed in linear time and correctly capture the cut-vertex / block incidence structure.
    Hopcroft–Tarjan cited; preprocessing of Theorem 3.2.
  • standard math Planar Monotone 3-SAT, Grid Tiling (parameterized by κ), and MAX-2SAT(3) are NP-/W[1]-/APX-complete as stated in the cited sources.
    Source problems for Theorems 4.1, 5.3, 4.8.
  • ad hoc to paper When |S| > n the surplus points may remain unused; hardness statements that require |S|=n can be recovered by dummy vertices that preserve the claimed graph class.
    Stated in the introduction and used to transfer some negative results; the dummy-vertex constructions are only sketched for matchings/trees and left open for paths/cycles.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Point Set Embeddability with List Constraints." pith.science (2026). https://pith.science/paper/6KECMFXL

@misc{pith2026260724182,
  author       = {Pith},
  title        = {Pith review of: Point Set Embeddability with List Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6KECMFXL}},
  note         = {Machine review of arXiv:2607.24182}
}
abstract

Deciding whether a given graph admits a planar straight-line drawing where each vertex is placed on some point from a given finite point set is known as Point Set Embeddability and is a classical problem in graph drawing. In this paper, we study the more general embeddability question where the placement of each vertex $v$ is restricted to a list $L(v)$ of admissible points. We first study the case where the given point set is in convex position. We show that this case is NP-hard even if the given graph is a matching and bi-labeled, i.e., each vertex has at most 2 admissible points. On the positive side, we present two efficient algorithms for the case where the given graph $G$ is connected (and not necessarily bi-labeled): if $G$ is equipped with a combinatorial embedding that needs to be respected, we can solve the problem in polynomial time; otherwise we can solve it in FPT-time with regard to the maximum vertex degree. In particular, this answers an open question by Frati, Glisse, Lenhart, Liotta, Mchedlidze, and Nishat [GD'13]. We then turn our attention to the more general case where the given point set is not necessarily in convex position. Here, we show NP-hardness for bi-labeled paths; notably these graphs have a unique combinatorial embedding and maximum degree two. We also present an FPT-algorithm with respect to the vertex cover number for the special case of bi-labeled graphs. We complement this latter result by establishing paraNP-hardness in the tri-labeled setting for vertex cover number 2 and polynomial-time solvability for vertex cover number 1 and arbitrary $L$. Finally, we study optimization and extension variants, where we want to maximize the number of edges or extend a partial drawing, respectively. For the former, we show APX-hardness and for the latter, we provide a parameterized complexity dichotomy under natural extension parameters.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

59 extracted references · 19 canonical work pages

  1. [1]

    On embedding an outer-planar graph in a point set , year =

    Bose, Prosenjit , journal =. On embedding an outer-planar graph in a point set , year =. doi:10.1016/s0925-7721(01)00069-4 , publisher =

    work page doi:10.1016/s0925-7721(01)00069-4

  2. [2]

    Planar embeddability of the vertices of a graph using a fixed point set is NP-hard , year =

    Cabello, Sergio , journal =. Planar embeddability of the vertices of a graph using a fixed point set is NP-hard , year =. doi:10.7155/jgaa.00132 , publisher =

    work page doi:10.7155/jgaa.00132

  3. [3]

    The point-set embeddability problem for plane graphs , year =

    Biedl, Therese and Vatshelle, Martin , booktitle =. The point-set embeddability problem for plane graphs , year =

  4. [4]

    On the Hardness of Point-Set Embeddability , year =

    Durocher, Stephane and Mondal, Debajyoti , booktitle =. On the Hardness of Point-Set Embeddability , year =. doi:10.1007/978-3-642-28076-4_16 , isbn =

    work page doi:10.1007/978-3-642-28076-4_16

  5. [5]

    , booktitle =

    Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Meijer, Henk and Trotta, Francesco and Wismath, Stephen K. , booktitle =. k-Colored Point-Set Embeddability of Outerplanar Graphs , year =. doi:10.1007/978-3-540-70904-6_31 , isbn =

    work page doi:10.1007/978-3-540-70904-6_31

  6. [6]

    Drawing Colored Graphs with Constrained Vertex Positions and Few Bends per Edge , year =

    Di Giacomo, Emilio and Liotta, Giuseppe and Trotta, Francesco , journal =. Drawing Colored Graphs with Constrained Vertex Positions and Few Bends per Edge , year =. doi:10.1007/s00453-008-9255-2 , publisher =

    work page doi:10.1007/s00453-008-9255-2

  7. [7]

    and Liotta, Giuseppe and Mchedlidze, Tamara and Nishat, Rahnuma Islam , booktitle =

    Frati, Fabrizio and Glisse, Marc and Lenhart, William J. and Liotta, Giuseppe and Mchedlidze, Tamara and Nishat, Rahnuma Islam , booktitle =. Point-Set Embeddability of 2-Colored Trees , year =. doi:10.1007/978-3-642-36763-2_26 , isbn =

    work page doi:10.1007/978-3-642-36763-2_26

  8. [8]

    Drawing Colored Graphs on Colored Points , year =

    Badent, Melanie and Di Giacomo, Emilio and Liotta, Giuseppe , booktitle =. Drawing Colored Graphs on Colored Points , year =. doi:10.1007/978-3-540-73951-7_10 , isbn =

    work page doi:10.1007/978-3-540-73951-7_10

Show all 59 references
  1. [9]

    Drawing colored graphs on colored points , year =

    Badent, Melanie and Di Giacomo, Emilio and Liotta, Giuseppe , journal =. Drawing colored graphs on colored points , year =. doi:10.1016/j.tcs.2008.08.004 , publisher =

    2008 doi

  2. [10]

    How to Embed a Path onto Two Sets of Points , year =

    Di Giacomo, Emilio and Liotta, Giuseppe and Trotta, Francesco , booktitle =. How to Embed a Path onto Two Sets of Points , year =. doi:10.1007/11618058_11 , isbn =

    doi

  3. [11]

    Simple alternating path problem , year =

    Akiyama, Jin and Urrutia, Jorge , journal =. Simple alternating path problem , year =. doi:10.1016/0012-365x(90)90276-n , publisher =

    doi

  4. [12]

    Optimal algorithms to embed trees in a point set , year =

    Bose, Prosenjit and McAllister, Michael and Snoeyink, Jack , booktitle =. Optimal algorithms to embed trees in a point set , year =. doi:10.1007/bfb0021791 , isbn =

    doi

  5. [13]

    Testing Planarity of Partially Embedded Graphs , year =

    Angelini, Patrizio and Di Battista, Giuseppe and Frati, Fabrizio and Jelínek, Vít and Kratochvíl, Jan and Patrignani, Maurizio and Rutter, Ignaz , journal =. Testing Planarity of Partially Embedded Graphs , year =. doi:10.1145/2629341 , publisher =

    doi

  6. [14]

    On Extending a Partial Straight-Line Drawing , year =

    Patrignani, Maurizio , pages =. On Extending a Partial Straight-Line Drawing , year =. Graph Drawing , doi =

  7. [15]

    Extending Convex Partial Drawings of Graphs , year =

    Mchedlidze, Tamara and Nöllenburg, Martin and Rutter, Ignaz , journal =. Extending Convex Partial Drawings of Graphs , year =. doi:10.1007/s00453-015-0018-6 , publisher =

    doi

  8. [16]

    2024 , copyright =

    Schaefer, Marcus and Cardinal, Jean and Miltzow, Tillmann , title =. 2024 , copyright =. doi:10.48550/ARXIV.2407.18006 , keywords =

    2024 doi arXiv

  9. [17]

    Point-Set Embedding of Trees with Edge Constraints , year =

    Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Meijer, Henk and Wismath, Stephen , booktitle =. Point-Set Embedding of Trees with Edge Constraints , year =. doi:10.1007/978-3-540-77537-9_14 , isbn =

    doi

  10. [18]

    , journal =

    Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Meijer, Henk and Wismath, Stephen K. , journal =. Point-set embeddings of trees with given partial drawings , year =. doi:10.1016/j.comgeo.2009.01.001 , publisher =

    2009 doi

  11. [19]

    Embedding Vertices at Points: Few Bends Suffice for Planar Graphs , year =

    Kaufmann, Michael and Wiese, Roland , booktitle =. Embedding Vertices at Points: Few Bends Suffice for Planar Graphs , year =. doi:10.1007/3-540-46648-7_17 , isbn =

    doi

  12. [20]

    Embedding Planar Graphs at Fixed Vertex Locations , year =

    Pach, János and Wenger, Rephael , journal =. Embedding Planar Graphs at Fixed Vertex Locations , year =. doi:10.1007/pl00007258 , publisher =

    doi

  13. [21]

    Constrained Point-Set Embeddability of Planar Graphs , year =

    Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Meijer, Henk and Wismath, Stephen , booktitle =. Constrained Point-Set Embeddability of Planar Graphs , year =. doi:10.1007/978-3-642-00219-9_35 , isbn =

    doi

  14. [22]

    The Complexity of Drawing a Graph in a Polygonal Region , year =

    Lubiw, Anna and Miltzow, Tillmann and Mondal, Debajyoti , booktitle =. The Complexity of Drawing a Graph in a Polygonal Region , year =. doi:10.1007/978-3-030-04414-5_28 , isbn =

    doi

  15. [23]

    Colored Point-Set Embeddings of Acyclic Graphs , year =

    Di Giacomo, Emilio and Gasieniec, Leszek and Liotta, Giuseppe and Navarra, Alfredo , booktitle =. Colored Point-Set Embeddings of Acyclic Graphs , year =. doi:10.1007/978-3-319-73915-1_32 , isbn =

    doi

  16. [24]

    On Embedding a Graph on Two Sets of Points , journal =

    Emilio. On Embedding a Graph on Two Sets of Points , journal =. 2006 , doi =

    2006

  17. [25]

    2012 , isbn =

    Reinhard Diestel , publisher =. 2012 , isbn =

    2012

  18. [26]

    Balanced Independent and Dominating Sets on Colored Interval Graphs , booktitle =

    Sujoy Bhore and Jan. Balanced Independent and Dominating Sets on Colored Interval Graphs , booktitle =. 2021 , doi =

    2021

  19. [27]

    1998 , publisher =

    Feige, Uriel , title =. 1998 , publisher =. doi:10.1145/285055.285059 , journal =

    1998

  20. [28]

    van Kreveld and Mark H

    Mark de Berg and Otfried Cheong and Marc J. van Kreveld and Mark H. Overmars , publisher =. Computational

  21. [29]

    Algorithms for Reporting and Counting Geometric Intersections , year =

    Jon Louis Bentley and Thomas Ottmann , journal =. Algorithms for Reporting and Counting Geometric Intersections , year =

  22. [30]

    Kanj and Ge Xia , journal =

    Jianer Chen and Iyad A. Kanj and Ge Xia , journal =. Improved upper bounds for vertex cover , year =

  23. [31]

    and Karp, Richard M

    Hopcroft, John E. and Karp, Richard M. , journal =. An n^. 1973 , number =

    1973

  24. [32]

    Fomin and Lukasz Kowalik and Daniel Lokshtanov and D

    Marek Cygan and Fedor V. Fomin and Lukasz Kowalik and Daniel Lokshtanov and D. Parameterized. 2015 , isbn =

    2015

  25. [33]

    Uriel Feige , title =. J. 1998 , url =

    1998

  26. [34]

    2001 , publisher=

    Approximation algorithms , author=. 2001 , publisher=

    2001

  27. [35]

    Optimal Binary Space Partitions in the Plane

    de Berg, Mark and Khosravi, Amirali. Optimal Binary Space Partitions in the Plane. Computing and Combinatorics. 2010

    2010

  28. [36]

    American Mathematical Monthly , year=

    Embedding a planar triangulation with vertices at specified points , author=. American Mathematical Monthly , year=

  29. [37]

    Straight Line Embeddings of Planar Graphs on Point Sets , year =

    Casta\. Straight Line Embeddings of Planar Graphs on Point Sets , year =. Proceedings of the 8th Canadian Conference on Computational Geometry , pages =

  30. [38]

    Patrizio Angelini and Till Bruckdorfer and Giuseppe Di Battista and Michael Kaufmann and Tamara Mchedlidze and Vincenzo Roselli and Claudio Squarcella , title =. Discret. Comput. Geom. , volume =. 2018 , doi =

    2018

  31. [39]

    Maciej Kurowski , title =. Inf. Process. Lett. , volume =. 2004 , doi =

    2004

  32. [40]

    Bannister and Zhanpeng Cheng and William E

    Michael J. Bannister and Zhanpeng Cheng and William E. Devanny and David Eppstein , title =. J. Graph Algorithms Appl. , volume =. 2014 , doi =

    2014

  33. [41]

    How to draw a planar graph on a grid , journal =

    Hubert de Fraysseix and J. How to draw a planar graph on a grid , journal =. 1990 , doi =

    1990

  34. [42]

    Embedding Planar Graphs on the Grid , booktitle =

    Walter Schnyder , editor =. Embedding Planar Graphs on the Grid , booktitle =

  35. [43]

    Jean Cardinal and Michael Hoffmann and Vincent Kusters , title =. J. Graph Algorithms Appl. , volume =. 2015 , doi =

    2015

  36. [44]

    Manfred Scheucher and Hendrik Schrezenmaier and Raphael Steiner , title =. J. Graph Algorithms Appl. , volume =. 2020 , doi =

    2020

  37. [45]

    On the curve complexity of 3-colored point-set embeddings , journal =

    Emilio. On the curve complexity of 3-colored point-set embeddings , journal =. 2020 , doi =

    2020

  38. [46]

    2-colored point-set embeddings of partial 2-trees , journal =

    Emilio. 2-colored point-set embeddings of partial 2-trees , journal =. 2021 , doi =

    2021

  39. [47]

    Chambers and David Eppstein and Michael T

    Erin W. Chambers and David Eppstein and Michael T. Goodrich and Maarten L. Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area , journal =. 2012 , doi =

    2012

  40. [48]

    M. R. Garey and David S. Johnson , title =. 1979 , isbn =

    1979

  41. [49]

    Automata, Languages, and Programming (ICALP'20) , Year =

    Eiben, Eduard and Ganian, Robert and Hamm, Thekla and Klute, Fabian and Nöllenburg, Martin , Title =. Automata, Languages, and Programming (ICALP'20) , Year =. doi:10.4230/LIPIcs.ICALP.2020.43 , Ee =

    2020 doi

  42. [50]

    and Ganian, Robert and Nöllenburg, Martin , Title =

    Depian, Thomas and Fink, Simon D. and Ganian, Robert and Nöllenburg, Martin , Title =. Graph Drawing and Network Visualization (GD'24) , Year =. doi:10.4230/LIPIcs.GD.2024.12 , Ee =

    2024 doi

  43. [51]

    Tarjan, Robert , title =. SIAM J. Comput. , year =

  44. [52]

    Efficient

    Hopcroft, John and Tarjan, Robert , journal =. Efficient. 1973 , number =

    1973

  45. [53]

    Graham , title =

    Ronald L. Graham , title =. Information Processing Letters , volume =. 1972 , doi =

    1972

  46. [54]

    Mitchell , title =

    Sandra L. Mitchell , title =. Information Processing Letters , volume =. 1979 , doi =

    1979

  47. [55]

    and Ganian, Robert and Nöllenburg, Martin , journal =

    Depian, Thomas and Fink, Simon D. and Ganian, Robert and Nöllenburg, Martin , journal =. The Parameterized Complexity Of Extending Stack Layouts , year =

  48. [56]

    Computational Geometry (SoCG'23) , Year =

    Bhore, Sujoy and Ganian, Robert and Khazaliya, Liana and Montecchiani, Fabrizio and Nöllenburg, Martin , Title =. Computational Geometry (SoCG'23) , Year =. doi:10.4230/LIPIcs.SoCG.2023.18 , Ee =

    2023 doi

  49. [57]

    Bhore, Sujoy and Ganian, Robert and Khazaliya, Liana and Montecchiani, Fabrizio and Nöllenburg, Martin , Title =. J. Computational Geometry , Year =

  50. [58]

    and Klemz, Boris and Ganian, Robert and Nöllenburg, Martin and Sieper, Marie Diana , Title =

    Depian, Thomas and Fink, Simon D. and Klemz, Boris and Ganian, Robert and Nöllenburg, Martin and Sieper, Marie Diana , Title =. Proc. 41st European Workshop on Computational Geometry (EuroCG'25) , Year =

  51. [59]

    Fink and Robert Ganian and Martin N

    Thomas Depian and Simon D. Fink and Robert Ganian and Martin N. Proc. 51st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'25) , title =. 2026 , doi =

    2026

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.