Computing maximum cliques in $B_2$-EPG graphs

Marc Heinrich; Nicolas Bousquet

RECORD

Computing maximum cliques in $B_2$-EPG graphs

Nicolas Bousquet, Marc Heinrich

Data Structures and Algorithms · Submitted 20 Jun 2017

abstract compiled · 2026-09-23 · no language-model review

The authors' main claim In this paper, we show that we can compute a maximum clique in polynomial time in $B_2$-EPG graphs given a representation of the graph.

how it is stated · asserted 1.00 read the record →

Comment (0) Read on arXiv ↗

Cite ▾

Claim paper

The compiled record

The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Open the compiled record

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 6,388 input tokens.

What the abstract itself states, as probabilities: claims first 0.11 · states limitation 0.73 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.97 · compares with prior results 0.95 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

EPG graphs, introduced by Golumbic et al. in 2009, are edge-intersection graphs of paths on an orthogonal grid. The class $B_k$-EPG is the subclass of EPG graphs where the path on the grid associated to each vertex has at most $k$ bends. Epstein et al. showed in 2013 that computing a maximum clique in $B_1$-EPG graphs is polynomial. As remarked in [Heldt et al., 2014], when the number of bends is at least $4$, the class contains $2$-interval graphs for which computing a maximum clique is an NP-hard problem. The complexity status of the Maximum Clique problem remains open for $B_2$ and $B_3$-EPG graphs. In this paper, we show that we can compute a maximum clique in polynomial time in $B_2$-EPG graphs given a representation of the graph. Moreover, we show that a simple counting argument provides a ${2(k+1)}$-approximation for the coloring problem on $B_k$-EPG graphs without knowing the representation of the graph. It generalizes a result of [Epstein et al, 2013] on $B_1$-EPG graphs (where the representation was needed).

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	EPG graphs, introduced by Golumbic et al. in 2009, are edge-intersection graphs of paths on an orthogonal grid.	background 1.00	0.03	0.01	asserted 1.00
s1	The class $B_k$-EPG is the subclass of EPG graphs where the path on the grid associated to each vertex has at most $k$ bends.	background 1.00	0.06	0.02	asserted 1.00
s2	Epstein et al. showed in 2013 that computing a maximum clique in $B_1$-EPG graphs is polynomial.	background 1.00	0.02	0.02	asserted 1.00
s3	As remarked in [Heldt et al., 2014], when the number of bends is at least $4$, the class contains $2$-interval graphs for which computing a maximum clique is an NP-hard problem.	background 0.91	0.03	0.01	asserted 1.00
s4	The complexity status of the Maximum Clique problem remains open for $B_2$ and $B_3$-EPG graphs.	gap 1.00	0.05	0.02	asserted 1.00
s5	In this paper, we show that we can compute a maximum clique in polynomial time in $B_2$-EPG graphs given a representation of the graph.	contribution 0.57	0.97	0.94	asserted 1.00
s6	Moreover, we show that a simple counting argument provides a ${2(k+1)}$-approximation for the coloring problem on $B_k$-EPG graphs without knowing the representation of the graph.	result 0.63	0.95	0.08	asserted 1.00
s7	It generalizes a result of [Epstein et al, 2013] on $B_1$-EPG graphs (where the representation was needed).	interpretation 0.89	0.46	0.04	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.84 · evidence from proof or derivation 0.99.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

The paper

Original abstract

EPG graphs, introduced by Golumbic et al. in 2009, are edge-intersection graphs of paths on an orthogonal grid. The class $B_k$-EPG is the subclass of EPG graphs where the path on the grid associated to each vertex has at most $k$ bends. Epstein et al. showed in 2013 that computing a maximum clique in $B_1$-EPG graphs is polynomial. As remarked in [Heldt et al., 2014], when the number of bends is at least $4$, the class contains $2$-interval graphs for which computing a maximum clique is an NP-hard problem. The complexity status of the Maximum Clique problem remains open for $B_2$ and $B_3$-EPG graphs. In this paper, we show that we can compute a maximum clique in polynomial time in $B_2$-EPG graphs given a representation of the graph. Moreover, we show that a simple counting argument provides a ${2(k+1)}$-approximation for the coloring problem on $B_k$-EPG graphs without knowing the representation of the graph. It generalizes a result of [Epstein et al, 2013] on $B_1$-EPG graphs (where the representation was needed).

Human review

How Pith checks papers → · Full audit of this paper →

Discussion

Know something about this paper? Leave a comment, or highlight any passage above to comment on it.