Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Alexandre Rok

dblp:139/1061 · DBLP profile ↗
← Back
6ranked-venue papers
5as first author
1since 2021 · last 2021
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 4 · 4 first-authorGraphics, computer vision, multimedia, augmented reality and games · 2 · 1 first-author · 1 since 2021

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
3 papers
Computational geometry · 56% Graph algorithms and graph theory · 35% Approximation and online algorithms · 9%

Topics — the 7 heaviest of 8, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Graph algorithms and graph theory › graph coloring
chi-boundedness
0.522017
Coloring Curves That Cross a Fixed Curve · SoCG 2017
Outerstring graphs are χ-bounded · SoCG 2014
Computational geometry › intersection graphs
geometric intersection graphs
0.522017
Coloring Curves That Cross a Fixed Curve · SoCG 2017
Outerstring graphs are χ-bounded · SoCG 2014
Graph algorithms and graph theory
graph coloring
0.522017
Coloring Curves That Cross a Fixed Curve · SoCG 2017
Outerstring graphs are χ-bounded · SoCG 2014
Computational geometry › intersection graphs
string graphs
0.312017
Coloring Curves That Cross a Fixed Curve · SoCG 2017
Approximation and online algorithms › approximation algorithms
geometric approximation
0.212016
Weak 1/r-Nets for Moving Points · SoCG 2016
Computational geometry › combinatorial geometry › geometric set systems
geometric hitting set
0.212016
Weak 1/r-Nets for Moving Points · SoCG 2016
Computational geometry › epsilon-net
weak epsilon-nets
0.212016
Weak 1/r-Nets for Moving Points · SoCG 2016

Methods — techniques the papers use, named apart from their topics

combinatorial coloring arguments · 0.5epsilon-net theory · 0.2
YearPublicationVenuePosition
2021 Conflict-Free Coloring of String Graphs
Chaya Keller, Alexandre Rok, Shakhar Smorodinsky
Discret. Comput. Geom.2
2019 Coloring Curves that Cross a Fixed Curve
abstract
We prove that for every integer $$t\geqslant 1$$ , the class of intersection graphs of curves in the plane each of which crosses a fixed curve in at least one and at most t points is $$\chi $$ -bounded. This is essentially the strongest $$\chi $$ -boundedness result one can get for those kind of graph classes. As a corollary, we prove that for any fixed integers $$k\geqslant 2$$ and $$t\geqslant 1$$ , every k-quasi-planar topological graph on n vertices with any two edges crossing at most t times has $$O(n\log n)$$ edges.
Alexandre Rok, Bartosz Walczak
Discret. Comput. Geom.1
2019 Outerstring Graphs are χ-Bounded
abstract
An outerstring graph is an intersection graph of curves that lie in a common half-plane and have one endpoint on the boundary of that half-plane. We prove that the class of outerstring graphs is $\chi$-bounded, which means that their chromatic number is bounded by a function of their clique number. This generalizes a series of previous results on $\chi$-boundedness of outerstring graphs with various additional restrictions on the shape of curves or the number of times the pairs of curves can cross. The assumption that each curve has an endpoint on the boundary of the half-plane is justified by the known fact that triangle-free intersection graphs of straight-line segments can have arbitrarily large chromatic number.
Alexandre Rok, Bartosz Walczak
SIAM J. Discret. Math.1
2017 Coloring Curves That Cross a Fixed Curve
Alexandre Rok, Bartosz Walczak
SoCG1
2016 Weak 1/r-Nets for Moving Points
Alexandre Rok, Shakhar Smorodinsky
SoCG1
2014 Outerstring graphs are χ-bounded
abstract
An outerstring graph is an intersection graph of curves lying in a halfplane with one endpoint on the boundary of the halfplane. It is proved that the outerstring graphs are χ-bounded, that is, their chromatic number is bounded by a function of their clique number. This generalizes a series of previous results on χ-boundedness of outerstring graphs with various restrictions of the shape of the curves or the number of times the pairs of curves can intersect. This also implies that the intersection graphs of x-monotone curves with bounded clique number have chromatic number O(log n), improving the previous polylogarithmic upper bound. The assumption that each curve has an endpoint on the boundary of the halfplane is justified by the known fact that triangle-free intersection graphs of straight-line segments can have arbitrarily large chromatic number.
Alexandre Rok, Bartosz Walczak
SoCG1