A Natural Quadratic Approach to the Generalized Graph Layering Problem

Sven Mallach

REVIEW 1 major objections 6 minor 12 references

A Natural Quadratic Approach to the Generalized Graph Layering Problem

T0 review · 1 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read A quadratic assignment model matches the best exact solvers for layered graph drawing.

desk verdict A clean new QAP formulation for layered graph drawing, but the GLP-W experiments use a layer bound that is not an upper bound, so the empirical claims address a height-bounded variant. read the letter →

arxiv 1908.04104 v1 pith:AOMZG3II submitted 2019-08-12 cs.DS cs.DM

Sven Mallach This is my paper · ORCID

classification cs.DScs.DM MSC 90C1090C2705C8568R10

keywords graphlayeringquadraticassignmentproblemmixed-integerprogrammingcompactlinearizationdrawingarcreversalminimumwidth

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 proposes new exact mixed-integer programming models, QLA-W and QLA-MS*, for the generalized graph layering problem, based on a quadratic assignment formulation. The models express arc reversals, dummy-vertex counts, width, and drawing-area scaling directly through quadratic terms that are linearized in a compact way. Computational experiments on AT&T and random graphs show these quadratic models are competitive with the previous ordering-based CGL models, with no clear winner overall. A sympathetic reader would care because this offers a more intuitive and potentially more extensible exact approach to a problem central to hierarchical graph drawing.

What carries the argument

The central object is the compact linearization of quadratic assignment constraints: for each arc $uv$ and layers $k,\ell$, a continuous variable $p_{u,k,v,\ell}$ is forced, by equations (2) and (3), to equal $x_{u,k} \cdot x_{v,\ell}$ whenever the $x$ variables are binary. Arc length, reversal, dummy-vertex counts, width, and inverse scaling factor are then expressed as sums of these $p$ variables, giving a model with only $2|A|Y + |V|$ constraints while avoiding artificial auxiliary variables for reversals and dummies.

What would settle it

On any small directed graph (e.g., three vertices forming a directed cycle) and a small layer bound $Y$, enumerate all binary assignments satisfying equations (1)-(4) and check whether every variable $p_{u,k,v,\ell}$ equals $x_{u,k} \cdot x_{v,\ell}$. If any feasible binary solution violates this equality, the objective can miscompute arc length or reversal counts, and the model would not solve the stated problem.

Watch

Extended reading notes

Core claim

The central claim is that the quadratic-assignment-based MIP models QLA-W and QLA-MS* are computationally competitive with the previously best exact ordering-based models CGL-W and CGL-MS* for the generalized graph layering problem. Using binary variables that assign each vertex to a layer, and continuous product variables defined for each arc and pair of layers, the model expresses arc length, reversal, dummy vertices, width, and target-area scaling as linear sums over those products. The compact linearization, taken from the author's earlier work, ensures each product variable equals the product of its two binary assignment variables at every feasible binary solution, so the objective faithfully represents the geometric quantities. The paper reports that solution times and timeout counts are comparable across instance families and objective settings, concluding that neither model family is clearly superior.

Load-bearing premise

The model is correct only if the cited compact linearization result indeed guarantees that each product variable equals the product of its two binary assignment variables at every feasible binary solution; the paper relies on that theorem from earlier work without proving it here.

Editorial extensions

If this is right

QLA-W and QLA-MS* can serve as drop-in exact alternatives to CGL-W and CGL-MS* when solving layered drawing problems with a general-purpose MIP solver.
The natural quadratic formulation makes it straightforward to add or adjust layout objectives, such as emphasizing width or fitting a specific drawing aspect ratio, without redesigning the model.
Experiments indicate that width-emphasized and aspect-ratio-constrained layering remain hard beyond about 50 vertices for all tested models, pointing to a common bottleneck rather than a model-specific weakness.
The 2:1 aspect-ratio case is consistently the hardest setting for both model families, suggesting that extreme aspect ratios impose particularly tight constraints on feasible layerings.
Because the model is assignment-based, it may more easily accommodate additional assignment-dependent constraints in future generalizations of the layering problem.

Reading between the lines

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

The competitive performance suggests that the difficulty of the QAP does not carry over to this special assignment structure; the compact constraint count may be more decisive than the quadratic nature.
The model could be adapted to other optimization problems with assignment constraints and pairwise interaction costs, such as scheduling or facility layout, where the same compact linearization applies.
Testing QLA-W on larger sparse graphs, or with different MIP solvers, would reveal whether the observed competitiveness is robust or tied to the specific solver and instance densities used.
The natural expression of reversals and dummy vertices might also inspire new heuristic approaches, since the quadratic formulation exposes the pairwise decisions directly.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

First, the thing you should know: this paper's quadratic assignment model for graph layering is real and clean, but the experiments quietly solve a height-bounded version of GLP-W because the chosen layer bound Y is not an upper bound. That doesn't kill the formulation, but it undercuts the headline claim of competitiveness on the unrestricted problem.

What's actually new: no prior QAP-based exact model exists for the generalized layering variants, and the product-variable encoding of arc length, reversals, dummy vertices, width, and scaling is natural and correct. The compact linearization from the author's earlier work [5] is cited rather than proved, but equations (2)-(3) do force p = x_u * x_v for binary x, so the math holds up. The model is compact in constraints and the paper is well structured.

The main soft spot is the choice of Y in Section 5.1. For GLP-W, there is no height restriction, so an exact formulation needs Y to be at least the number of layers used by an optimal layering; |V| is a safe bound. Setting Y = ceil(1.6*sqrt(|V|)), as done "as in [4]", is not a bound. A directed path on 60 vertices has an optimal GLP-W layering using 60 layers, and forcing it into 13 layers forces reversals with high penalty. So the runtimes in Figure 3 do not solve the problem defined in Section 2; they solve a height-bounded variant. The head-to-head with CGL-W is still fair because both use the same Y, but the abstract's claim of an exact approach to the generalized problem is overstated.

A second, lesser issue: there is no code or data, and the comparison is based on aggregated plots without per-instance results or statistical detail. That makes the empirical claims hard to verify. The paper's own conclusion acknowledges the size limitation, which is honest.

Who is this for: researchers working on exact MIP models for layered graph drawing. The formulation is a genuinely new tool and the paper is worth a serious referee. I would not cite it for the experimental claim, but I'd cite it for the QLA model itself.

Recommendation: send it to peer review, but ask for a revision that either uses a valid Y or explicitly states that the experiments target the height-bounded variant. The core contribution is sound; the experimental claim needs recalibration.

Referee Report

1 major / 6 minor

Summary. The paper proposes two mixed-integer programming formulations, QLA-W and QLA-MS*, for the generalized graph layering problem with width minimization (GLP-W) and with adaptation to a target drawing area (GLP-MS*). The models use binary assignment variables x_{v,k} for the layer of each vertex and continuous product variables p_{u,k,v,l} intended to equal x_{u,k} x_{v,l}; equations (1)-(4) enforce a feasible layering, and the objective terms for arc length, reversed arcs, dummy vertices, width, and scaling factor are expressed linearly through these products, following a compact linearization theorem from the author's earlier paper [5]. The paper reports computational experiments comparing QLA-W with CGL-W and QLA-MS* with CGL-MS* on AT&T and random graphs with up to 60 vertices, using Gurobi with a half-hour time limit, and concludes that the quadratic-assignment-based models are computationally competitive with the prior exact models.

Significance. If the computational claims are valid, the paper offers a conceptually natural exact modeling alternative to the ordering-based CGL formulations: the QAP-style model expresses conjunctive layout conditions directly and is compact in the number of constraints. The modeling core is largely correct: for binary x variables, equations (2)-(3) force p_{u,k,v,l} = x_{u,k} x_{v,l}, and the derivations of arc length, reversal indicators, and dummy-vertex counts in Section 4 are sound. The GLP-MS* experiments are not affected by the main concern below because they use the valid bound Y = |V|. However, the experimental evidence for GLP-W is compromised by the choice of Y in Section 5.1, and the paper does not provide code or data for independent reproduction. The approach remains promising, but the empirical support for the central competitiveness claim on GLP-W needs to be corrected before the claim can be accepted.

major comments (1)

[§5.1, Experiment (1), and §4.1] The choice Y = ceil(1.6 sqrt(|V|)) is not an upper bound on the number of layers needed by an optimal GLP-W solution, so the model solved in Figure 3 is a height-bounded variant of GLP-W rather than the problem defined in Problem 4. Section 4.1 explicitly requires Y to be an upper bound on the number of layers, but Experiment (1) sets Y without any instance-specific justification. For example, a directed path on 60 vertices has an optimal layering under the weights of Experiment (1) that uses 60 layers, width 1, total length 59, and no reversals, giving objective value 60; forcing Y = 13 would require at least one reversal at cost omega_rev = 13 * 59 = 767, so the two optima are far apart. Thus the reported QLA-W and CGL-W runtimes do not establish that either model solves GLP-W as defined. Please either re-run the GLP-W experiments with a valid bound such as Y = |V|, or justify a valid instance-specific upper bound and state explicitly that the comparison is for a height-bounded variant.

minor comments (6)

[§4.1] The stated total number of product variables is incorrect: after omitting the diagonal variables p_{u,k,v,k}, there are |A| * Y * (Y-1) such variables, not |A| * (Y-1)^2. Please correct or clarify the counting convention.
[§5] The experiments report only solution times and timeout counts. Reporting optimal objective values, or final optimality gaps for timed-out instances, would let readers verify that QLA and CGL solve the same instance to the same optimum and would strengthen the equivalence claim.
[§5.1] The sentence 'Gurobi 5 (release version 8)' is inconsistent; the solver should be identified as Gurobi 8 or as 'Gurobi (release version 8)'.
[§2] The statement that width minimization can be obtained by setting r_W = 1 and r_H = infinity is informal, since the normalized ratios introduced in the paper are finite; a limiting or explicit degenerate-case statement would be more precise.
[§5.1] In the description of the first instance set, 'The first set ATTar are the AT&T graphs' appears to contain a typo; 'ATTar' should likely be 'AT&T'.
[§4.1] Since equations (2)-(3) rely on the compact linearization theorem from [5], a short statement of the lemma, or a precise pointer to the theorem in [5], would make the paper more self-contained.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the QLA models derive their objective from a cited, independent linearization theorem and are validated against external benchmark MIPs.

full rationale

The paper's derivation chain is self-contained with respect to its central claim. The quadratic model expresses arc length, reversals, and dummy-vertex counts through product variables p_{u,k,v,l}, and equations (2)-(3) force p = x_u,k * x_v,l for binary x. This relies on the author's earlier compact-linearization result [5], but that is a general, parameter-free theorem about assignment-constrained quadratic programs, not a restatement of the layering result; it does not assume the target objective or the GLP solution. The computational claim is an empirical comparison against the previously published CGL-W and CGL-MS* models on standard benchmark sets, with no fitted parameters relabeled as predictions. The reviewer-flagged issue that Y = ceil(1.6 sqrt(|V|)) may not be a valid height upper bound for unrestricted GLP-W is a modeling-validity concern about the experimental setup, not a circular derivation: the models themselves do not define their correctness in terms of the chosen Y. The paper's use of settings 'as in [4]' and 'as in [8]' is a reproducibility choice, not a load-bearing self-citation that forces the conclusion. Therefore no circular step is exhibited, and the appropriate score is 0.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The model introduces no new physical or mathematical entities beyond auxiliary optimization variables. It relies on the compact linearization theorem from the author's prior work, on the user-supplied layer bound Y, and on the standard width proxy used throughout the graph layering literature.

free parameters (2)

Layer bound Y = ceil(1.6 * sqrt(|V|)) for GLP-W; |V| for GLP-MS*
Chosen a priori following the experimental setup of [4] and [8]. The model only considers layerings using at most Y layers, so if the true optimum needs more layers, the computed solution is optimal for the restricted problem only.
Objective weights (omega_len, omega_rev, omega_wid, omega_scl) = omega_len=1, omega_rev=Y*|A|, omega_wid=1 or omega_rev*|A|+|A|*Y+1, omega_scl=omega_rev*|A|+|A|*Y+1
Hand-selected to match the priorities used in prior studies [4,8]. They define the trade-offs between edge length, reversals, width, and scaling, and the empirical comparison is conditioned on them.

assumptions (3)

standard math Compact linearization theorem (Mallach 2018): for binary x satisfying assignment constraints, p variables satisfying equations (2)-(3) equal products x_{u,k} x_{v,l}.
Invoked in Section 4.1 to justify the product variables; all arc-length, reversal, and dummy-vertex terms in the model rely on this equality.
domain assumption The chosen layer bound Y is a valid upper bound for an optimal layering of the instances tested.
Set to ceil(1.6*sqrt(|V|)) or |V| in Section 5.1. If Y is too small, the model is infeasible or returns the optimum for a restricted problem, so the experiments only support the comparison under these bounds.
domain assumption Width of a layering is the maximum number of original and dummy vertices on any layer; this is a proxy for final drawing width.
Used in the definitions of DLP-W and GLP-W in Section 2; the final width also depends on horizontal coordinate assignment and arc routing, as the paper acknowledges.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Natural Quadratic Approach to the Generalized Graph Layering Problem." pith.science (2026). https://pith.science/paper/AOMZG3II

@misc{pith2026190804104,
  author       = {Pith},
  title        = {Pith review of: A Natural Quadratic Approach to the Generalized Graph Layering Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AOMZG3II}},
  note         = {Machine review of arXiv:1908.04104}
}

read the original abstract

We propose a new exact approach to the generalized graph layering problem that is based on a particular quadratic assignment formulation. It expresses, in a natural way, the associated layout restrictions and several possible objectives, such as a minimum total arc length, minimum number of reversed arcs, and minimum width, or the adaptation to a specific drawing area. Our computational experiments show a competitive performance compared to prior exact models.

Figures

Figures reproduced from arXiv: 1908.04104 by the authors.

**Figure 1.** Two layered drawings of the same directed acyclic graph. On the left a classic one, i.e., adhering to its longest path with all arcs pointing downwards, and on the right with a better aspect ratio achieved by reversing only two arcs (drawn dash-dotted). In this paper, we present a new exact approach to integrate vertex layering, the feedback arc set problem, and width or drawing area optimization. Its most appealing… view at source ↗

**Figure 2.** A directed graph drawn based on a layering created by solving GLP-MS with the ratio rW : rH set to 1 : 2 (left), 1 : 1 (middle), and 2 : 1 (right). The obtained optimal W : H combinations are respectively 5 : 10, 6 : 6, and 8 : 4. Formally, define H := maxv∈V L(v) to be the height of a layering L. This definition is suitable as we may assume w.l.o.g. (and, if necessary, enforce a posteriori for any given and feasib… view at source ↗

**Figure 3.** The plots depict the solution times in seconds (a cross per graph) for GLP with neglected (1) and emphasized width minimization (2). Crosses at the top (1800s) correspond to timeouts, their quantities are given to the left of the respective cross. 5.2 GLP-MS∗ In this experiment, the parameters are set (almost) as in [8]: Y = |V |, ωlen = 1, ωrev = Y ωlen|A|, and ωscl = ωrev|A| + |A| · Y + 1. Priorities are thus the … view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: The plots depict the solution times in seconds (a cross per graph) for the different rH : rW combinations. Crosses at the top (1800s) correspond to timeouts, their quantities are given to the left of the respective cross. there are instance subsets and rH : rW ratios w…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 7 canonical work pages

[5]

4OR 16(3), 295--309 (Sep 2018)

Mallach, S.: Compact linearization for binary quadratic problems subject to assignment constraints. 4OR 16(3), 295--309 (Sep 2018). doi:10.1007/s10288-017-0364-0

work page doi:10.1007/s10288-017-0364-0 2018
[4]

u egg, U., von Hanxleden, R.: Compact layered drawings of general directed graphs. In: Hu, Y., N \

Jabrayilov, A., Mallach, S., Mutzel, P., R \"u egg, U., von Hanxleden, R.: Compact layered drawings of general directed graphs. In: Hu, Y., N \"o llenburg, M. (eds.) Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD'16). pp. 209--221. Springer, Cham (2016)

work page 2016
[1]

In: Proceedings of the Symposium on Graph Drawing (GD'96), LNCS, vol

Di Battista , G., Garg, A., Liotta, G., Parise, A., Tamassia, R., Tassinari, E., Vargiu, F., Vismara, L.: Drawing directed acyclic graphs: An experimental study. In: Proceedings of the Symposium on Graph Drawing (GD'96), LNCS, vol. 1190, pp. 76--91. Springer (1997)

work page 1997
[2]

Software Engineering 19(3), 214--230 (1993)

Gansner, E.R., Koutsofios, E., North, S.C., Vo, K.P.: A technique for drawing directed graphs. Software Engineering 19(3), 214--230 (1993)

work page 1993
[3]

In: Goodrich, M.T., Kobourov, S.G

Healy, P., Nikolov, N.S.: A branch-and-cut approach to the directed acyclic graph layering problem. In: Goodrich, M.T., Kobourov, S.G. (eds.) Proceedings of the 10th International Symposium on Graph Drawing (GD'02), LNCS, vol. 2528, pp. 98--109. Springer (2002). doi:10.1007/3-540-36151-0

doi:10.1007/3-540-36151-0 2002
[6]

u egg, U., Ehlers, T., Sp \

R \"u egg, U., Ehlers, T., Sp \"o nemann, M., von Hanxleden, R.: A generalization of the directed graph layering problem. Technical Report 1501, Kiel University, Department of Computer Science (Feb 2015), ISSN 2192-6247

work page 2015
[7]

u egg, U., Ehlers, T., Sp \

R \"u egg, U., Ehlers, T., Sp \"o nemann, M., von Hanxleden, R.: A generalization of the directed graph layering problem. In: Hu, Y., N \"o llenburg, M. (eds.) Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD'16). pp. 196--208. Springer, Cham (2016)

work page 2016
[8]

uegg , U., Ehlers , T., Sp\

R\"uegg , U., Ehlers , T., Sp\"onemann , M., von Hanxleden , R.: Generalized layerings for arbitrary and fixed drawing areas. Journal of Graph Algorithms and Applications 21(5), 823--856 (2017). doi:10.7155/jgaa.00441

doi:10.7155/jgaa.00441 2017

Show all 12 references

[9]

IEEE Transactions on Systems, Man and Cybernetics 11(2), 109--125 (Feb 1981)

Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man and Cybernetics 11(2), 109--125 (Feb 1981)

1981
[10]

Journal of Computer and System Sciences 10(3), 384--393 (1975)

Ullman, J.D.: NP -complete scheduling problems. Journal of Computer and System Sciences 10(3), 384--393 (1975). doi:https://doi.org/10.1016/S0022-0000(75)80008-0

1975 doi
[11]

, " * write output.state after.block = add.period write

ENTRY address author booktitle chapter doi edition editor eid howpublished institution journal key month note number organization pages publisher school series title type url volume year label INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION in...
[12]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [5]

4OR 16(3), 295--309 (Sep 2018)

Mallach, S.: Compact linearization for binary quadratic problems subject to assignment constraints. 4OR 16(3), 295--309 (Sep 2018). doi:10.1007/s10288-017-0364-0

work page doi:10.1007/s10288-017-0364-0 2018

[2] [4]

u egg, U., von Hanxleden, R.: Compact layered drawings of general directed graphs. In: Hu, Y., N \

Jabrayilov, A., Mallach, S., Mutzel, P., R \"u egg, U., von Hanxleden, R.: Compact layered drawings of general directed graphs. In: Hu, Y., N \"o llenburg, M. (eds.) Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD'16). pp. 209--221. Springer, Cham (2016)

work page 2016

[3] [1]

In: Proceedings of the Symposium on Graph Drawing (GD'96), LNCS, vol

Di Battista , G., Garg, A., Liotta, G., Parise, A., Tamassia, R., Tassinari, E., Vargiu, F., Vismara, L.: Drawing directed acyclic graphs: An experimental study. In: Proceedings of the Symposium on Graph Drawing (GD'96), LNCS, vol. 1190, pp. 76--91. Springer (1997)

work page 1997

[4] [2]

Software Engineering 19(3), 214--230 (1993)

Gansner, E.R., Koutsofios, E., North, S.C., Vo, K.P.: A technique for drawing directed graphs. Software Engineering 19(3), 214--230 (1993)

work page 1993

[5] [3]

In: Goodrich, M.T., Kobourov, S.G

Healy, P., Nikolov, N.S.: A branch-and-cut approach to the directed acyclic graph layering problem. In: Goodrich, M.T., Kobourov, S.G. (eds.) Proceedings of the 10th International Symposium on Graph Drawing (GD'02), LNCS, vol. 2528, pp. 98--109. Springer (2002). doi:10.1007/3-540-36151-0

doi:10.1007/3-540-36151-0 2002

[6] [6]

u egg, U., Ehlers, T., Sp \

R \"u egg, U., Ehlers, T., Sp \"o nemann, M., von Hanxleden, R.: A generalization of the directed graph layering problem. Technical Report 1501, Kiel University, Department of Computer Science (Feb 2015), ISSN 2192-6247

work page 2015

[7] [7]

u egg, U., Ehlers, T., Sp \

R \"u egg, U., Ehlers, T., Sp \"o nemann, M., von Hanxleden, R.: A generalization of the directed graph layering problem. In: Hu, Y., N \"o llenburg, M. (eds.) Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD'16). pp. 196--208. Springer, Cham (2016)

work page 2016

[8] [8]

uegg , U., Ehlers , T., Sp\

R\"uegg , U., Ehlers , T., Sp\"onemann , M., von Hanxleden , R.: Generalized layerings for arbitrary and fixed drawing areas. Journal of Graph Algorithms and Applications 21(5), 823--856 (2017). doi:10.7155/jgaa.00441

doi:10.7155/jgaa.00441 2017