---
_id: '13974'
abstract:
- lang: eng
text: The Tverberg theorem is one of the cornerstones of discrete geometry. It states
that, given a set X of at least (d+1)(r−1)+1 points in Rd, one can find a partition
X=X1∪⋯∪Xr of X, such that the convex hulls of the Xi, i=1,…,r, all share a common
point. In this paper, we prove a trengthening of this theorem that guarantees
a partition which, in addition to the above, has the property that the boundaries
of full-dimensional convex hulls have pairwise nonempty intersections. Possible
generalizations and algorithmic aspects are also discussed. As a concrete application,
we show that any n points in the plane in general position span ⌊n/3⌋ vertex-disjoint
triangles that are pairwise crossing, meaning that their boundaries have pairwise
nonempty intersections; this number is clearly best possible. A previous result
of Álvarez-Rebollar et al. guarantees ⌊n/6⌋pairwise crossing triangles. Our result
generalizes to a result about simplices in Rd, d≥2.
acknowledgement: "Part of the research leading to this paper was done during the 16th
Gremo Workshop on Open Problems (GWOP), Waltensburg, Switzerland, June 12–16, 2018.
We thank Patrick Schnider for suggesting the problem, and Stefan Felsner, Malte
Milatz, and Emo Welzl for fruitful discussions during the workshop. We also thank
Stefan Felsner and Manfred Scheucher for finding, communicating the example from
Sect. 3.3, and the kind permission to include their visualization of the point set.
We thank Dömötör Pálvölgyi, the SoCG reviewers, and DCG reviewers for various helpful
comments.\r\nR. Fulek gratefully acknowledges support from Austrian Science Fund
(FWF), Project M2281-N35. A. Kupavskii was supported by the Advanced Postdoc.Mobility
Grant no. P300P2_177839 of the Swiss National Science Foundation. Research by P.
Valtr was supported by the Grant no. 18-19158 S of the Czech Science Foundation
(GAČR)."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Bernd
full_name: Gärtner, Bernd
last_name: Gärtner
- first_name: Andrey
full_name: Kupavskii, Andrey
last_name: Kupavskii
- first_name: Pavel
full_name: Valtr, Pavel
last_name: Valtr
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem.
Discrete and Computational Geometry. 2023. doi:10.1007/s00454-023-00532-x
apa: Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2023).
The crossing Tverberg theorem. Discrete and Computational Geometry. Springer
Nature. https://doi.org/10.1007/s00454-023-00532-x
chicago: Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli
Wagner. “The Crossing Tverberg Theorem.” Discrete and Computational Geometry.
Springer Nature, 2023. https://doi.org/10.1007/s00454-023-00532-x.
ieee: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing
Tverberg theorem,” Discrete and Computational Geometry. Springer Nature,
2023.
ista: Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2023. The crossing Tverberg
theorem. Discrete and Computational Geometry.
mla: Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” Discrete and Computational
Geometry, Springer Nature, 2023, doi:10.1007/s00454-023-00532-x.
short: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, Discrete and Computational
Geometry (2023).
date_created: 2023-08-06T22:01:12Z
date_published: 2023-07-27T00:00:00Z
date_updated: 2023-12-13T12:03:35Z
day: '27'
department:
- _id: UlWa
doi: 10.1007/s00454-023-00532-x
external_id:
arxiv:
- '1812.04911'
isi:
- '001038546500001'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1812.04911
month: '07'
oa: 1
oa_version: Preprint
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: epub_ahead
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '6647'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: The crossing Tverberg theorem
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '11593'
abstract:
- lang: eng
text: 'A drawing of a graph on a surface is independently even if every pair of
nonadjacent edges in the drawing crosses an even number of times. The Z2 -genus
of a graph G is the minimum g such that G has an independently even drawing on
the orientable surface of genus g. An unpublished result by Robertson and Seymour
implies that for every t, every graph of sufficiently large genus contains as
a minor a projective t×t grid or one of the following so-called t -Kuratowski
graphs: K3,t, or t copies of K5 or K3,3 sharing at most two common vertices. We
show that the Z2-genus of graphs in these families is unbounded in t; in fact,
equal to their genus. Together, this implies that the genus of a graph is bounded
from above by a function of its Z2-genus, solving a problem posed by Schaefer
and Štefankovič, and giving an approximate version of the Hanani–Tutte theorem
on orientable surfaces. We also obtain an analogous result for Euler genus and
Euler Z2-genus of graphs.'
acknowledgement: "We thank Zdeněk Dvořák, Xavier Goaoc, and Pavel Paták for helpful
discussions. We also thank Bojan Mohar, Paul Seymour, Gelasio Salazar, Jim Geelen,
and John Maharry for information about their unpublished results related to Conjecture
3.1. Finally we thank the reviewers for corrections and suggestions for improving
the presentation.\r\nSupported by Austrian Science Fund (FWF): M2281-N35. Supported
by project 19-04113Y of the Czech Science Foundation (GAČR), by the Czech-French
collaboration project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM), and by Charles University
project UNCE/SCI/004."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Jan
full_name: Kynčl, Jan
last_name: Kynčl
citation:
ama: Fulek R, Kynčl J. The Z2-Genus of Kuratowski minors. Discrete and Computational
Geometry. 2022;68:425-447. doi:10.1007/s00454-022-00412-w
apa: Fulek, R., & Kynčl, J. (2022). The Z2-Genus of Kuratowski minors. Discrete
and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00412-w
chicago: Fulek, Radoslav, and Jan Kynčl. “The Z2-Genus of Kuratowski Minors.” Discrete
and Computational Geometry. Springer Nature, 2022. https://doi.org/10.1007/s00454-022-00412-w.
ieee: R. Fulek and J. Kynčl, “The Z2-Genus of Kuratowski minors,” Discrete and
Computational Geometry, vol. 68. Springer Nature, pp. 425–447, 2022.
ista: Fulek R, Kynčl J. 2022. The Z2-Genus of Kuratowski minors. Discrete and Computational
Geometry. 68, 425–447.
mla: Fulek, Radoslav, and Jan Kynčl. “The Z2-Genus of Kuratowski Minors.” Discrete
and Computational Geometry, vol. 68, Springer Nature, 2022, pp. 425–47, doi:10.1007/s00454-022-00412-w.
short: R. Fulek, J. Kynčl, Discrete and Computational Geometry 68 (2022) 425–447.
date_created: 2022-07-17T22:01:56Z
date_published: 2022-09-01T00:00:00Z
date_updated: 2023-08-14T12:43:52Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-022-00412-w
external_id:
arxiv:
- '1803.05085'
isi:
- '000825014500001'
intvolume: ' 68'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1803.05085
month: '09'
oa: 1
oa_version: Preprint
page: 425-447
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '186'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: The Z2-Genus of Kuratowski minors
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 68
year: '2022'
...
---
_id: '6647'
abstract:
- lang: eng
text: The Tverberg theorem is one of the cornerstones of discrete geometry. It states
that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition
X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r,
all share a common point. In this paper, we prove a strengthening of this theorem
that guarantees a partition which, in addition to the above, has the property
that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections.
Possible generalizations and algorithmic aspects are also discussed. As a concrete
application, we show that any n points in the plane in general position span floor[n/3]
vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries
have pairwise nonempty intersections; this number is clearly best possible. A
previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing
triangles. Our result generalizes to a result about simplices in R^d,d >=2.
alternative_title:
- LIPIcs
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Bernd
full_name: Gärtner, Bernd
last_name: Gärtner
- first_name: Andrey
full_name: Kupavskii, Andrey
last_name: Kupavskii
- first_name: Pavel
full_name: Valtr, Pavel
last_name: Valtr
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg
theorem. In: 35th International Symposium on Computational Geometry. Vol
129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:38:1-38:13. doi:10.4230/LIPICS.SOCG.2019.38'
apa: 'Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2019).
The crossing Tverberg theorem. In 35th International Symposium on Computational
Geometry (Vol. 129, p. 38:1-38:13). Portland, OR, United States: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.38'
chicago: Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli
Wagner. “The Crossing Tverberg Theorem.” In 35th International Symposium on
Computational Geometry, 129:38:1-38:13. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2019. https://doi.org/10.4230/LIPICS.SOCG.2019.38.
ieee: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing
Tverberg theorem,” in 35th International Symposium on Computational Geometry,
Portland, OR, United States, 2019, vol. 129, p. 38:1-38:13.
ista: 'Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2019. The crossing Tverberg
theorem. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium
on Computational Geometry, LIPIcs, vol. 129, 38:1-38:13.'
mla: Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” 35th International
Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2019, p. 38:1-38:13, doi:10.4230/LIPICS.SOCG.2019.38.
short: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, in:, 35th International
Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2019, p. 38:1-38:13.
conference:
end_date: 2019-06-21
location: Portland, OR, United States
name: 'SoCG 2019: Symposium on Computational Geometry'
start_date: 2019-06-18
date_created: 2019-07-17T10:35:04Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-12-13T12:03:35Z
day: '01'
ddc:
- '000'
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPICS.SOCG.2019.38
external_id:
arxiv:
- '1812.04911'
file:
- access_level: open_access
checksum: d6d017f8b41291b94d102294fa96ae9c
content_type: application/pdf
creator: dernst
date_created: 2019-07-24T06:54:52Z
date_updated: 2020-07-14T12:47:35Z
file_id: '6667'
file_name: 2019_LIPICS_Fulek.pdf
file_size: 559837
relation: main_file
file_date_updated: 2020-07-14T12:47:35Z
has_accepted_license: '1'
intvolume: ' 129'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 38:1-38:13
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: 35th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959771047'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '13974'
relation: later_version
status: public
scopus_import: 1
status: public
title: The crossing Tverberg theorem
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 129
year: '2019'
...
---
_id: '6982'
abstract:
- lang: eng
text: "We present an efficient algorithm for a problem in the interface between
clustering and graph embeddings. An embedding ϕ : G → M of a graph G into a 2-manifold
M maps the vertices in V(G) to distinct points and the edges in E(G) to interior-disjoint
Jordan arcs between the corresponding vertices. In applications in clustering,
cartography, and visualization, nearby vertices and edges are often bundled to
the same point or overlapping arcs due to data compression or low resolution.
This raises the computational problem of deciding whether a given map ϕ : G →
M comes from an embedding. A map ϕ : G → M is a weak embedding if it can be perturbed
into an embedding ψ ϵ : G → M with ‖ ϕ − ψ ϵ ‖ < ϵ for every ϵ > 0, where ‖.‖
is the unform norm.\r\nA polynomial-time algorithm for recognizing weak embeddings
has recently been found by Fulek and Kynčl. It reduces the problem to solving
a system of linear equations over Z2. It runs in O(n2ω)≤ O(n4.75) time, where
ω ∈ [2,2.373) is the matrix multiplication exponent and n is the number of vertices
and edges of G. We improve the running time to O(n log n). Our algorithm is also
conceptually simpler: We perform a sequence of local operations that gradually
“untangles” the image ϕ(G) into an embedding ψ(G) or reports that ϕ is not a weak
embedding. It combines local constraints on the orientation of subgraphs directly,
thereby eliminating the need for solving large systems of linear equations.\r\n"
article_number: '50'
article_type: original
arxiv: 1
author:
- first_name: Hugo
full_name: Akitaya, Hugo
last_name: Akitaya
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Csaba
full_name: Tóth, Csaba
last_name: Tóth
citation:
ama: Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. ACM Transactions
on Algorithms. 2019;15(4). doi:10.1145/3344549
apa: Akitaya, H., Fulek, R., & Tóth, C. (2019). Recognizing weak embeddings
of graphs. ACM Transactions on Algorithms. ACM. https://doi.org/10.1145/3344549
chicago: Akitaya, Hugo, Radoslav Fulek, and Csaba Tóth. “Recognizing Weak Embeddings
of Graphs.” ACM Transactions on Algorithms. ACM, 2019. https://doi.org/10.1145/3344549.
ieee: H. Akitaya, R. Fulek, and C. Tóth, “Recognizing weak embeddings of graphs,”
ACM Transactions on Algorithms, vol. 15, no. 4. ACM, 2019.
ista: Akitaya H, Fulek R, Tóth C. 2019. Recognizing weak embeddings of graphs. ACM
Transactions on Algorithms. 15(4), 50.
mla: Akitaya, Hugo, et al. “Recognizing Weak Embeddings of Graphs.” ACM Transactions
on Algorithms, vol. 15, no. 4, 50, ACM, 2019, doi:10.1145/3344549.
short: H. Akitaya, R. Fulek, C. Tóth, ACM Transactions on Algorithms 15 (2019).
date_created: 2019-11-04T15:45:17Z
date_published: 2019-10-01T00:00:00Z
date_updated: 2023-09-15T12:19:31Z
day: '01'
department:
- _id: UlWa
doi: 10.1145/3344549
external_id:
arxiv:
- '1709.09209'
intvolume: ' 15'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1709.09209
month: '10'
oa: 1
oa_version: Preprint
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: ACM Transactions on Algorithms
publication_status: published
publisher: ACM
quality_controlled: '1'
related_material:
record:
- id: '309'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Recognizing weak embeddings of graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2019'
...
---
_id: '7034'
abstract:
- lang: eng
text: We find a graph of genus 5 and its drawing on the orientable surface of genus
4 with every pair of independent edges crossing an even number of times. This
shows that the strong Hanani–Tutte theorem cannot be extended to the orientable
surface of genus 4. As a base step in the construction we use a counterexample
to an extension of the unified Hanani–Tutte theorem on the torus.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Jan
full_name: Kynčl, Jan
last_name: Kynčl
citation:
ama: Fulek R, Kynčl J. Counterexample to an extension of the Hanani-Tutte theorem
on the surface of genus 4. Combinatorica. 2019;39(6):1267-1279. doi:10.1007/s00493-019-3905-7
apa: Fulek, R., & Kynčl, J. (2019). Counterexample to an extension of the Hanani-Tutte
theorem on the surface of genus 4. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-019-3905-7
chicago: Fulek, Radoslav, and Jan Kynčl. “Counterexample to an Extension of the
Hanani-Tutte Theorem on the Surface of Genus 4.” Combinatorica. Springer
Nature, 2019. https://doi.org/10.1007/s00493-019-3905-7.
ieee: R. Fulek and J. Kynčl, “Counterexample to an extension of the Hanani-Tutte
theorem on the surface of genus 4,” Combinatorica, vol. 39, no. 6. Springer
Nature, pp. 1267–1279, 2019.
ista: Fulek R, Kynčl J. 2019. Counterexample to an extension of the Hanani-Tutte
theorem on the surface of genus 4. Combinatorica. 39(6), 1267–1279.
mla: Fulek, Radoslav, and Jan Kynčl. “Counterexample to an Extension of the Hanani-Tutte
Theorem on the Surface of Genus 4.” Combinatorica, vol. 39, no. 6, Springer
Nature, 2019, pp. 1267–79, doi:10.1007/s00493-019-3905-7.
short: R. Fulek, J. Kynčl, Combinatorica 39 (2019) 1267–1279.
date_created: 2019-11-18T14:29:50Z
date_published: 2019-10-29T00:00:00Z
date_updated: 2023-08-30T07:26:25Z
day: '29'
department:
- _id: UlWa
doi: 10.1007/s00493-019-3905-7
ec_funded: 1
external_id:
arxiv:
- '1709.00508'
isi:
- '000493267200003'
intvolume: ' 39'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1709.00508
month: '10'
oa: 1
oa_version: Preprint
page: 1267-1279
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: Combinatorica
publication_identifier:
eissn:
- 1439-6912
issn:
- 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Counterexample to an extension of the Hanani-Tutte theorem on the surface of
genus 4
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 39
year: '2019'
...
---
_id: '7401'
abstract:
- lang: eng
text: 'The genus g(G) of a graph G is the minimum g such that G has an embedding
on the orientable surface M_g of genus g. A drawing of a graph on a surface is
independently even if every pair of nonadjacent edges in the drawing crosses an
even number of times. The Z_2-genus of a graph G, denoted by g_0(G), is the minimum
g such that G has an independently even drawing on M_g. By a result of Battle,
Harary, Kodama and Youngs from 1962, the graph genus is additive over 2-connected
blocks. In 2013, Schaefer and Stefankovic proved that the Z_2-genus of a graph
is additive over 2-connected blocks as well, and asked whether this result can
be extended to so-called 2-amalgamations, as an analogue of results by Decker,
Glover, Huneke, and Stahl for the genus. We give the following partial answer.
If G=G_1 cup G_2, G_1 and G_2 intersect in two vertices u and v, and G-u-v has
k connected components (among which we count the edge uv if present), then |g_0(G)-(g_0(G_1)+g_0(G_2))|<=k+1.
For complete bipartite graphs K_{m,n}, with n >= m >= 3, we prove that g_0(K_{m,n})/g(K_{m,n})=1-O(1/n).
Similar results are proved also for the Euler Z_2-genus. We express the Z_2-genus
of a graph using the minimum rank of partial symmetric matrices over Z_2; a problem
that might be of independent interest. '
alternative_title:
- LIPIcs
article_number: '39'
article_processing_charge: No
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Jan
full_name: Kyncl, Jan
last_name: Kyncl
citation:
ama: 'Fulek R, Kyncl J. Z_2-Genus of graphs and minimum rank of partial symmetric
matrices. In: 35th International Symposium on Computational Geometry (SoCG
2019). Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.SOCG.2019.39'
apa: 'Fulek, R., & Kyncl, J. (2019). Z_2-Genus of graphs and minimum rank of
partial symmetric matrices. In 35th International Symposium on Computational
Geometry (SoCG 2019) (Vol. 129). Portland, OR, United States: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.39'
chicago: Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of
Partial Symmetric Matrices.” In 35th International Symposium on Computational
Geometry (SoCG 2019), Vol. 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2019. https://doi.org/10.4230/LIPICS.SOCG.2019.39.
ieee: R. Fulek and J. Kyncl, “Z_2-Genus of graphs and minimum rank of partial symmetric
matrices,” in 35th International Symposium on Computational Geometry (SoCG
2019), Portland, OR, United States, 2019, vol. 129.
ista: 'Fulek R, Kyncl J. 2019. Z_2-Genus of graphs and minimum rank of partial symmetric
matrices. 35th International Symposium on Computational Geometry (SoCG 2019).
SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 39.'
mla: Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of Partial
Symmetric Matrices.” 35th International Symposium on Computational Geometry
(SoCG 2019), vol. 129, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2019, doi:10.4230/LIPICS.SOCG.2019.39.
short: R. Fulek, J. Kyncl, in:, 35th International Symposium on Computational Geometry
(SoCG 2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
conference:
end_date: 2019-06-21
location: Portland, OR, United States
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2019-06-18
date_created: 2020-01-29T16:17:05Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2021-01-12T08:13:24Z
day: '01'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.4230/LIPICS.SOCG.2019.39
external_id:
arxiv:
- '1903.08637'
file:
- access_level: open_access
checksum: aac37b09118cc0ab58cf77129e691f8c
content_type: application/pdf
creator: dernst
date_created: 2020-02-04T09:14:31Z
date_updated: 2020-07-14T12:47:57Z
file_id: '7445'
file_name: 2019_LIPIcs_Fulek.pdf
file_size: 628347
relation: main_file
file_date_updated: 2020-07-14T12:47:57Z
has_accepted_license: '1'
intvolume: ' 129'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: 35th International Symposium on Computational Geometry (SoCG 2019)
publication_identifier:
isbn:
- 978-3-95977-104-7
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Z_2-Genus of graphs and minimum rank of partial symmetric matrices
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 129
year: '2019'
...
---
_id: '5790'
abstract:
- lang: eng
text: The partial representation extension problem is a recently introduced generalization
of the recognition problem. A circle graph is an intersection graph of chords
of a circle. We study the partial representation extension problem for circle
graphs, where the input consists of a graph G and a partial representation R′
giving some predrawn chords that represent an induced subgraph of G. The question
is whether one can extend R′ to a representation R of the entire graph G, that
is, whether one can draw the remaining chords into a partially predrawn representation
to obtain a representation of G. Our main result is an O(n3) time algorithm for
partial representation extension of circle graphs, where n is the number of vertices.
To show this, we describe the structure of all representations of a circle graph
using split decomposition. This can be of independent interest.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Steven
full_name: Chaplick, Steven
last_name: Chaplick
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Pavel
full_name: Klavík, Pavel
last_name: Klavík
citation:
ama: Chaplick S, Fulek R, Klavík P. Extending partial representations of circle
graphs. Journal of Graph Theory. 2019;91(4):365-394. doi:10.1002/jgt.22436
apa: Chaplick, S., Fulek, R., & Klavík, P. (2019). Extending partial representations
of circle graphs. Journal of Graph Theory. Wiley. https://doi.org/10.1002/jgt.22436
chicago: Chaplick, Steven, Radoslav Fulek, and Pavel Klavík. “Extending Partial
Representations of Circle Graphs.” Journal of Graph Theory. Wiley, 2019.
https://doi.org/10.1002/jgt.22436.
ieee: S. Chaplick, R. Fulek, and P. Klavík, “Extending partial representations of
circle graphs,” Journal of Graph Theory, vol. 91, no. 4. Wiley, pp. 365–394,
2019.
ista: Chaplick S, Fulek R, Klavík P. 2019. Extending partial representations of
circle graphs. Journal of Graph Theory. 91(4), 365–394.
mla: Chaplick, Steven, et al. “Extending Partial Representations of Circle Graphs.”
Journal of Graph Theory, vol. 91, no. 4, Wiley, 2019, pp. 365–94, doi:10.1002/jgt.22436.
short: S. Chaplick, R. Fulek, P. Klavík, Journal of Graph Theory 91 (2019) 365–394.
date_created: 2018-12-30T22:59:15Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2023-08-24T14:30:43Z
day: '01'
department:
- _id: UlWa
doi: 10.1002/jgt.22436
ec_funded: 1
external_id:
arxiv:
- '1309.2399'
isi:
- '000485392800004'
intvolume: ' 91'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1309.2399
month: '08'
oa: 1
oa_version: Preprint
page: 365-394
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Journal of Graph Theory
publication_identifier:
issn:
- '03649024'
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extending partial representations of circle graphs
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 91
year: '2019'
...
---
_id: '5857'
abstract:
- lang: eng
text: 'A thrackle is a graph drawn in the plane so that every pair of its edges
meet exactly once: either at a common end vertex or in a proper crossing. We prove
that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are
defined similarly, except that every pair of edges that do not share a vertex
are allowed to cross an odd number of times. It is also shown that the maximum
number of edges of a quasi-thrackle on n vertices is [Formula presented](n−1),
and that this bound is best possible for infinitely many values of n.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: János
full_name: Pach, János
last_name: Pach
citation:
ama: 'Fulek R, Pach J. Thrackles: An improved upper bound. Discrete Applied Mathematics.
2019;259(4):266-231. doi:10.1016/j.dam.2018.12.025'
apa: 'Fulek, R., & Pach, J. (2019). Thrackles: An improved upper bound. Discrete
Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2018.12.025'
chicago: 'Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.”
Discrete Applied Mathematics. Elsevier, 2019. https://doi.org/10.1016/j.dam.2018.12.025.'
ieee: 'R. Fulek and J. Pach, “Thrackles: An improved upper bound,” Discrete Applied
Mathematics, vol. 259, no. 4. Elsevier, pp. 266–231, 2019.'
ista: 'Fulek R, Pach J. 2019. Thrackles: An improved upper bound. Discrete Applied
Mathematics. 259(4), 266–231.'
mla: 'Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” Discrete
Applied Mathematics, vol. 259, no. 4, Elsevier, 2019, pp. 266–231, doi:10.1016/j.dam.2018.12.025.'
short: R. Fulek, J. Pach, Discrete Applied Mathematics 259 (2019) 266–231.
date_created: 2019-01-20T22:59:17Z
date_published: 2019-04-30T00:00:00Z
date_updated: 2023-08-24T14:39:33Z
day: '30'
department:
- _id: UlWa
doi: 10.1016/j.dam.2018.12.025
external_id:
arxiv:
- '1708.08037'
isi:
- '000466061100020'
intvolume: ' 259'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1708.08037
month: '04'
oa: 1
oa_version: Preprint
page: 266-231
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: Discrete Applied Mathematics
publication_identifier:
issn:
- 0166218X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '433'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: 'Thrackles: An improved upper bound'
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 259
year: '2019'
...
---
_id: '309'
abstract:
- lang: eng
text: 'We present an efficient algorithm for a problem in the interface between
clustering and graph embeddings. An embedding '' : G ! M of a graph G into a 2manifold
M maps the vertices in V (G) to distinct points and the edges in E(G) to interior-disjoint
Jordan arcs between the corresponding vertices. In applications in clustering,
cartography, and visualization, nearby vertices and edges are often bundled to
a common node or arc, due to data compression or low resolution. This raises the
computational problem of deciding whether a given map '' : G ! M comes from an
embedding. A map '' : G ! M is a weak embedding if it can be perturbed into an
embedding ψ: G ! M with k'' "k < " for every " > 0. A polynomial-time
algorithm for recognizing weak embeddings was recently found by Fulek and Kyncl
[14], which reduces to solving a system of linear equations over Z2. It runs in
O(n2!) O(n4:75) time, where 2:373 is the matrix multiplication exponent and n
is the number of vertices and edges of G. We improve the running time to O(n log
n). Our algorithm is also conceptually simpler than [14]: We perform a sequence
of local operations that gradually "untangles" the image ''(G) into
an embedding (G), or reports that '' is not a weak embedding. It generalizes a
recent technique developed for the case that G is a cycle and the embedding is
a simple polygon [1], and combines local constraints on the orientation of subgraphs
directly, thereby eliminating the need for solving large systems of linear equations.'
acknowledgement: '∗Research supported in part by the NSF awards CCF-1422311 and CCF-1423615,
and the Science Without Borders program. The second author gratefully acknowledges
support from Austrian Science Fund (FWF): M2281-N35.'
article_processing_charge: No
arxiv: 1
author:
- first_name: Hugo
full_name: Akitaya, Hugo
last_name: Akitaya
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Csaba
full_name: Tóth, Csaba
last_name: Tóth
citation:
ama: 'Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. In: ACM;
2018:274-292. doi:10.1137/1.9781611975031.20'
apa: 'Akitaya, H., Fulek, R., & Tóth, C. (2018). Recognizing weak embeddings
of graphs (pp. 274–292). Presented at the SODA: Symposium on Discrete Algorithms,
New Orleans, LA, USA: ACM. https://doi.org/10.1137/1.9781611975031.20'
chicago: Akitaya, Hugo, Radoslav Fulek, and Csaba Tóth. “Recognizing Weak Embeddings
of Graphs,” 274–92. ACM, 2018. https://doi.org/10.1137/1.9781611975031.20.
ieee: 'H. Akitaya, R. Fulek, and C. Tóth, “Recognizing weak embeddings of graphs,”
presented at the SODA: Symposium on Discrete Algorithms, New Orleans, LA, USA,
2018, pp. 274–292.'
ista: 'Akitaya H, Fulek R, Tóth C. 2018. Recognizing weak embeddings of graphs.
SODA: Symposium on Discrete Algorithms, 274–292.'
mla: Akitaya, Hugo, et al. Recognizing Weak Embeddings of Graphs. ACM, 2018,
pp. 274–92, doi:10.1137/1.9781611975031.20.
short: H. Akitaya, R. Fulek, C. Tóth, in:, ACM, 2018, pp. 274–292.
conference:
end_date: 2018-01-10
location: New Orleans, LA, USA
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2018-01-07
date_created: 2018-12-11T11:45:45Z
date_published: 2018-01-01T00:00:00Z
date_updated: 2023-09-15T12:19:32Z
day: '01'
department:
- _id: UlWa
doi: 10.1137/1.9781611975031.20
external_id:
arxiv:
- '1709.09209'
isi:
- '000483921200021'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1709.09209
month: '01'
oa: 1
oa_version: Preprint
page: 274 - 292
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication_status: published
publisher: ACM
publist_id: '7556'
quality_controlled: '1'
related_material:
record:
- id: '6982'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Recognizing weak embeddings of graphs
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...
---
_id: '185'
abstract:
- lang: eng
text: We resolve in the affirmative conjectures of A. Skopenkov and Repovš (1998),
and M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the
setting of approximating maps of graphs on 2-dimensional surfaces by embeddings.
Our proof of this result is constructive and almost immediately implies an efficient
algorithm for testing whether a given piecewise linear map of a graph in a surface
is approximable by an embedding. More precisely, an instance of this problem consists
of (i) a graph G whose vertices are partitioned into clusters and whose inter-cluster
edges are partitioned into bundles, and (ii) a region R of a 2-dimensional compact
surface M given as the union of a set of pairwise disjoint discs corresponding
to the clusters and a set of pairwise disjoint "pipes" corresponding
to the bundles, connecting certain pairs of these discs. We are to decide whether
G can be embedded inside M so that the vertices in every cluster are drawn in
the corresponding disc, the edges in every bundle pass only through its corresponding
pipe, and every edge crosses the boundary of each disc at most once.
alternative_title:
- Leibniz International Proceedings in Information, LIPIcs
article_number: '39'
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Jan
full_name: Kynčl, Jan
last_name: Kynčl
citation:
ama: 'Fulek R, Kynčl J. Hanani-Tutte for approximating maps of graphs. In: Vol 99.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPIcs.SoCG.2018.39'
apa: 'Fulek, R., & Kynčl, J. (2018). Hanani-Tutte for approximating maps of
graphs (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry,
Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.39'
chicago: Fulek, Radoslav, and Jan Kynčl. “Hanani-Tutte for Approximating Maps of
Graphs,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.39.
ieee: 'R. Fulek and J. Kynčl, “Hanani-Tutte for approximating maps of graphs,” presented
at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol.
99.'
ista: 'Fulek R, Kynčl J. 2018. Hanani-Tutte for approximating maps of graphs. SoCG:
Symposium on Computational Geometry, Leibniz International Proceedings in Information,
LIPIcs, vol. 99, 39.'
mla: Fulek, Radoslav, and Jan Kynčl. Hanani-Tutte for Approximating Maps of Graphs.
Vol. 99, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPIcs.SoCG.2018.39.
short: R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2018.
conference:
end_date: 2018-06-14
location: Budapest, Hungary
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2018-06-11
date_created: 2018-12-11T11:45:04Z
date_published: 2018-01-01T00:00:00Z
date_updated: 2021-01-12T06:53:36Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2018.39
file:
- access_level: open_access
checksum: f1b94f1a75b37c414a1f61d59fb2cd4c
content_type: application/pdf
creator: dernst
date_created: 2018-12-17T12:33:52Z
date_updated: 2020-07-14T12:45:19Z
file_id: '5701'
file_name: 2018_LIPIcs_Fulek.pdf
file_size: 718857
relation: main_file
file_date_updated: 2020-07-14T12:45:19Z
has_accepted_license: '1'
intvolume: ' 99'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication_identifier:
isbn:
- 978-3-95977-066-8
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7735'
quality_controlled: '1'
scopus_import: 1
status: public
title: Hanani-Tutte for approximating maps of graphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 99
year: '2018'
...
---
_id: '186'
abstract:
- lang: eng
text: 'A drawing of a graph on a surface is independently even if every pair of
nonadjacent edges in the drawing crosses an even number of times. The ℤ2-genus
of a graph G is the minimum g such that G has an independently even drawing on
the orientable surface of genus g. An unpublished result by Robertson and Seymour
implies that for every t, every graph of sufficiently large genus contains as
a minor a projective t × t grid or one of the following so-called t-Kuratowski
graphs: K3, t, or t copies of K5 or K3,3 sharing at most 2 common vertices. We
show that the ℤ2-genus of graphs in these families is unbounded in t; in fact,
equal to their genus. Together, this implies that the genus of a graph is bounded
from above by a function of its ℤ2-genus, solving a problem posed by Schaefer
and Štefankovič, and giving an approximate version of the Hanani-Tutte theorem
on orientable surfaces.'
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Jan
full_name: Kynčl, Jan
last_name: Kynčl
citation:
ama: 'Fulek R, Kynčl J. The ℤ2-Genus of Kuratowski minors. In: Vol 99. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2018:40.1-40.14. doi:10.4230/LIPIcs.SoCG.2018.40'
apa: 'Fulek, R., & Kynčl, J. (2018). The ℤ2-Genus of Kuratowski minors (Vol.
99, p. 40.1-40.14). Presented at the SoCG: Symposium on Computational Geometry,
Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.40'
chicago: Fulek, Radoslav, and Jan Kynčl. “The ℤ2-Genus of Kuratowski Minors,” 99:40.1-40.14.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.40.
ieee: 'R. Fulek and J. Kynčl, “The ℤ2-Genus of Kuratowski minors,” presented at
the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99,
p. 40.1-40.14.'
ista: 'Fulek R, Kynčl J. 2018. The ℤ2-Genus of Kuratowski minors. SoCG: Symposium
on Computational Geometry, LIPIcs, vol. 99, 40.1-40.14.'
mla: Fulek, Radoslav, and Jan Kynčl. The ℤ2-Genus of Kuratowski Minors. Vol.
99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 40.1-40.14, doi:10.4230/LIPIcs.SoCG.2018.40.
short: R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2018, p. 40.1-40.14.
conference:
end_date: 2018-06-14
location: Budapest, Hungary
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2018-06-11
date_created: 2018-12-11T11:45:05Z
date_published: 2018-06-11T00:00:00Z
date_updated: 2023-08-14T12:43:51Z
day: '11'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2018.40
external_id:
arxiv:
- '1803.05085'
intvolume: ' 99'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1803.05085
month: '06'
oa: 1
oa_version: Submitted Version
page: 40.1 - 40.14
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7734'
quality_controlled: '1'
related_material:
record:
- id: '11593'
relation: later_version
status: public
scopus_import: '1'
status: public
title: The ℤ2-Genus of Kuratowski minors
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 99
year: '2018'
...
---
_id: '5791'
abstract:
- lang: eng
text: Due to data compression or low resolution, nearby vertices and edges of a
graph drawing may be bundled to a common node or arc. We model such a “compromised”
drawing by a piecewise linear map φ:G → ℝ. We wish to perturb φ by an arbitrarily
small ε>0 into a proper drawing (in which the vertices are distinct points, any
two edges intersect in finitely many points, and no three edges have a common
interior point) that minimizes the number of crossings. An ε-perturbation, for
every ε>0, is given by a piecewise linear map (Formula Presented), where with
||·|| is the uniform norm (i.e., sup norm). We present a polynomial-time solution
for this optimization problem when G is a cycle and the map φ has no spurs (i.e.,
no two adjacent edges are mapped to overlapping arcs). We also show that the problem
becomes NP-complete (i) when G is an arbitrary graph and φ has no spurs, and (ii)
when φ may have spurs and G is a cycle or a union of disjoint paths.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Csaba D.
full_name: Tóth, Csaba D.
last_name: Tóth
citation:
ama: 'Fulek R, Tóth CD. Crossing minimization in perturbed drawings. In: Vol 11282.
Springer; 2018:229-241. doi:10.1007/978-3-030-04414-5_16'
apa: 'Fulek, R., & Tóth, C. D. (2018). Crossing minimization in perturbed drawings
(Vol. 11282, pp. 229–241). Presented at the Graph Drawing and Network Visualization,
Barcelona, Spain: Springer. https://doi.org/10.1007/978-3-030-04414-5_16'
chicago: Fulek, Radoslav, and Csaba D. Tóth. “Crossing Minimization in Perturbed
Drawings,” 11282:229–41. Springer, 2018. https://doi.org/10.1007/978-3-030-04414-5_16.
ieee: R. Fulek and C. D. Tóth, “Crossing minimization in perturbed drawings,” presented
at the Graph Drawing and Network Visualization, Barcelona, Spain, 2018, vol. 11282,
pp. 229–241.
ista: Fulek R, Tóth CD. 2018. Crossing minimization in perturbed drawings. Graph
Drawing and Network Visualization, LNCS, vol. 11282, 229–241.
mla: Fulek, Radoslav, and Csaba D. Tóth. Crossing Minimization in Perturbed Drawings.
Vol. 11282, Springer, 2018, pp. 229–41, doi:10.1007/978-3-030-04414-5_16.
short: R. Fulek, C.D. Tóth, in:, Springer, 2018, pp. 229–241.
conference:
end_date: 2018-09-28
location: Barcelona, Spain
name: Graph Drawing and Network Visualization
start_date: 2018-09-26
date_created: 2018-12-30T22:59:15Z
date_published: 2018-12-18T00:00:00Z
date_updated: 2023-09-11T12:49:55Z
day: '18'
department:
- _id: UlWa
doi: 10.1007/978-3-030-04414-5_16
external_id:
arxiv:
- '1808.07608'
isi:
- '000672802500016'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1808.07608
month: '12'
oa: 1
oa_version: Preprint
page: 229-241
publication_identifier:
isbn:
- '9783030044138'
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Crossing minimization in perturbed drawings
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: '11282 '
year: '2018'
...
---
_id: '433'
abstract:
- lang: eng
text: 'A thrackle is a graph drawn in the plane so that every pair of its edges
meet exactly once: either at a common end vertex or in a proper crossing. We prove
that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are
defined similarly, except that every pair of edges that do not share a vertex
are allowed to cross an odd number of times. It is also shown that the maximum
number of edges of a quasi-thrackle on n vertices is 3/2(n-1), and that this bound
is best possible for infinitely many values of n.'
alternative_title:
- LNCS
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: János
full_name: Pach, János
last_name: Pach
citation:
ama: 'Fulek R, Pach J. Thrackles: An improved upper bound. In: Vol 10692. Springer;
2018:160-166. doi:10.1007/978-3-319-73915-1_14'
apa: 'Fulek, R., & Pach, J. (2018). Thrackles: An improved upper bound (Vol.
10692, pp. 160–166). Presented at the GD 2017: Graph Drawing and Network Visualization,
Boston, MA, United States: Springer. https://doi.org/10.1007/978-3-319-73915-1_14'
chicago: 'Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound,”
10692:160–66. Springer, 2018. https://doi.org/10.1007/978-3-319-73915-1_14.'
ieee: 'R. Fulek and J. Pach, “Thrackles: An improved upper bound,” presented at
the GD 2017: Graph Drawing and Network Visualization, Boston, MA, United States,
2018, vol. 10692, pp. 160–166.'
ista: 'Fulek R, Pach J. 2018. Thrackles: An improved upper bound. GD 2017: Graph
Drawing and Network Visualization, LNCS, vol. 10692, 160–166.'
mla: 'Fulek, Radoslav, and János Pach. Thrackles: An Improved Upper Bound.
Vol. 10692, Springer, 2018, pp. 160–66, doi:10.1007/978-3-319-73915-1_14.'
short: R. Fulek, J. Pach, in:, Springer, 2018, pp. 160–166.
conference:
end_date: 2017-09-27
location: Boston, MA, United States
name: 'GD 2017: Graph Drawing and Network Visualization'
start_date: 201-09-25
date_created: 2018-12-11T11:46:27Z
date_published: 2018-01-21T00:00:00Z
date_updated: 2023-08-24T14:39:32Z
day: '21'
department:
- _id: UlWa
doi: 10.1007/978-3-319-73915-1_14
external_id:
arxiv:
- '1708.08037'
intvolume: ' 10692'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1708.08037
month: '01'
oa: 1
oa_version: Submitted Version
page: 160 - 166
publication_status: published
publisher: Springer
publist_id: '7390'
quality_controlled: '1'
related_material:
record:
- id: '5857'
relation: later_version
status: public
scopus_import: 1
status: public
title: 'Thrackles: An improved upper bound'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10692
year: '2018'
...
---
_id: '1113'
abstract:
- lang: eng
text: 'A drawing of a graph G is radial if the vertices of G are placed on concentric
circles C 1 , . . . , C k with common center c , and edges are drawn radially
: every edge intersects every circle centered at c at most once. G is radial planar
if it has a radial embedding, that is, a crossing-free radial drawing. If the
vertices of G are ordered or partitioned into ordered levels (as they are for
leveled graphs), we require that the assignment of vertices to circles corresponds
to the given ordering or leveling. We show that a graph G is radial planar if
G has a radial drawing in which every two edges cross an even number of times;
the radial embedding has the same leveling as the radial drawing. In other words,
we establish the weak variant of the Hanani-Tutte theorem for radial planarity.
This generalizes a result by Pach and Toth.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Michael
full_name: Pelsmajer, Michael
last_name: Pelsmajer
- first_name: Marcus
full_name: Schaefer, Marcus
last_name: Schaefer
citation:
ama: Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity. Journal
of Graph Algorithms and Applications. 2017;21(1):135-154. doi:10.7155/jgaa.00408
apa: Fulek, R., Pelsmajer, M., & Schaefer, M. (2017). Hanani-Tutte for radial
planarity. Journal of Graph Algorithms and Applications. Brown University.
https://doi.org/10.7155/jgaa.00408
chicago: Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte
for Radial Planarity.” Journal of Graph Algorithms and Applications. Brown
University, 2017. https://doi.org/10.7155/jgaa.00408.
ieee: R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity,”
Journal of Graph Algorithms and Applications, vol. 21, no. 1. Brown University,
pp. 135–154, 2017.
ista: Fulek R, Pelsmajer M, Schaefer M. 2017. Hanani-Tutte for radial planarity.
Journal of Graph Algorithms and Applications. 21(1), 135–154.
mla: Fulek, Radoslav, et al. “Hanani-Tutte for Radial Planarity.” Journal of
Graph Algorithms and Applications, vol. 21, no. 1, Brown University, 2017,
pp. 135–54, doi:10.7155/jgaa.00408.
short: R. Fulek, M. Pelsmajer, M. Schaefer, Journal of Graph Algorithms and Applications
21 (2017) 135–154.
date_created: 2018-12-11T11:50:13Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-02-23T10:05:57Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.7155/jgaa.00408
ec_funded: 1
external_id:
arxiv:
- '1608.08662'
file:
- access_level: open_access
content_type: application/pdf
creator: dernst
date_created: 2019-10-24T10:54:37Z
date_updated: 2019-10-24T10:54:37Z
file_id: '6967'
file_name: 2017_JournalGraphAlgorithms_Fulek.pdf
file_size: 573623
relation: main_file
success: 1
file_date_updated: 2019-10-24T10:54:37Z
has_accepted_license: '1'
intvolume: ' 21'
issue: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 135 - 154
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Journal of Graph Algorithms and Applications
publication_status: published
publisher: Brown University
publist_id: '6254'
quality_controlled: '1'
related_material:
record:
- id: '1164'
relation: earlier_version
status: public
- id: '1595'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Hanani-Tutte for radial planarity
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 21
year: '2017'
...
---
_id: '793'
abstract:
- lang: eng
text: 'Let P be a finite point set in the plane. A cordinary triangle in P is a
subset of P consisting of three non-collinear points such that each of the three
lines determined by the three points contains at most c points of P . Motivated
by a question of Erdös, and answering a question of de Zeeuw, we prove that there
exists a constant c > 0such that P contains a c-ordinary triangle, provided
that P is not contained in the union of two lines. Furthermore, the number of
c-ordinary triangles in P is Ω(| P |). '
article_processing_charge: No
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Hossein
full_name: Mojarrad, Hossein
last_name: Mojarrad
- first_name: Márton
full_name: Naszódi, Márton
last_name: Naszódi
- first_name: József
full_name: Solymosi, József
last_name: Solymosi
- first_name: Sebastian
full_name: Stich, Sebastian
last_name: Stich
- first_name: May
full_name: Szedlák, May
last_name: Szedlák
citation:
ama: 'Fulek R, Mojarrad H, Naszódi M, Solymosi J, Stich S, Szedlák M. On the existence
of ordinary triangles. Computational Geometry: Theory and Applications.
2017;66:28-31. doi:10.1016/j.comgeo.2017.07.002'
apa: 'Fulek, R., Mojarrad, H., Naszódi, M., Solymosi, J., Stich, S., & Szedlák,
M. (2017). On the existence of ordinary triangles. Computational Geometry:
Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2017.07.002'
chicago: 'Fulek, Radoslav, Hossein Mojarrad, Márton Naszódi, József Solymosi, Sebastian
Stich, and May Szedlák. “On the Existence of Ordinary Triangles.” Computational
Geometry: Theory and Applications. Elsevier, 2017. https://doi.org/10.1016/j.comgeo.2017.07.002.'
ieee: 'R. Fulek, H. Mojarrad, M. Naszódi, J. Solymosi, S. Stich, and M. Szedlák,
“On the existence of ordinary triangles,” Computational Geometry: Theory and
Applications, vol. 66. Elsevier, pp. 28–31, 2017.'
ista: 'Fulek R, Mojarrad H, Naszódi M, Solymosi J, Stich S, Szedlák M. 2017. On
the existence of ordinary triangles. Computational Geometry: Theory and Applications.
66, 28–31.'
mla: 'Fulek, Radoslav, et al. “On the Existence of Ordinary Triangles.” Computational
Geometry: Theory and Applications, vol. 66, Elsevier, 2017, pp. 28–31, doi:10.1016/j.comgeo.2017.07.002.'
short: 'R. Fulek, H. Mojarrad, M. Naszódi, J. Solymosi, S. Stich, M. Szedlák, Computational
Geometry: Theory and Applications 66 (2017) 28–31.'
date_created: 2018-12-11T11:48:32Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-09-27T12:15:16Z
day: '01'
department:
- _id: UlWa
doi: 10.1016/j.comgeo.2017.07.002
ec_funded: 1
external_id:
isi:
- '000412039700003'
intvolume: ' 66'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1701.08183
month: '01'
oa: 1
oa_version: Submitted Version
page: 28 - 31
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
issn:
- '09257721'
publication_status: published
publisher: Elsevier
publist_id: '6861'
quality_controlled: '1'
status: public
title: On the existence of ordinary triangles
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 66
year: '2017'
...
---
_id: '794'
abstract:
- lang: eng
text: We show that c-planarity is solvable in quadratic time for flat clustered
graphs with three clusters if the combinatorial embedding of the underlying graph
is fixed. In simpler graph-theoretical terms our result can be viewed as follows.
Given a graph G with the vertex set partitioned into three parts embedded on a
2-sphere, our algorithm decides if we can augment G by adding edges without creating
an edge-crossing so that in the resulting spherical graph the vertices of each
part induce a connected sub-graph. We proceed by a reduction to the problem of
testing the existence of a perfect matching in planar bipartite graphs. We formulate
our result in a slightly more general setting of cyclic clustered graphs, i.e.,
the simple graph obtained by contracting each cluster, where we disregard loops
and multi-edges, is a cycle.
acknowledgement: I would like to thank Jan Kynčl, Dömötör Pálvölgyi and anonymous
referees for many comments and suggestions that helped to improve the presentation
of the result.
article_processing_charge: No
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
citation:
ama: 'Fulek R. C-planarity of embedded cyclic c-graphs. Computational Geometry:
Theory and Applications. 2017;66:1-13. doi:10.1016/j.comgeo.2017.06.016'
apa: 'Fulek, R. (2017). C-planarity of embedded cyclic c-graphs. Computational
Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2017.06.016'
chicago: 'Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs.” Computational
Geometry: Theory and Applications. Elsevier, 2017. https://doi.org/10.1016/j.comgeo.2017.06.016.'
ieee: 'R. Fulek, “C-planarity of embedded cyclic c-graphs,” Computational Geometry:
Theory and Applications, vol. 66. Elsevier, pp. 1–13, 2017.'
ista: 'Fulek R. 2017. C-planarity of embedded cyclic c-graphs. Computational Geometry:
Theory and Applications. 66, 1–13.'
mla: 'Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs.” Computational
Geometry: Theory and Applications, vol. 66, Elsevier, 2017, pp. 1–13, doi:10.1016/j.comgeo.2017.06.016.'
short: 'R. Fulek, Computational Geometry: Theory and Applications 66 (2017) 1–13.'
date_created: 2018-12-11T11:48:32Z
date_published: 2017-12-01T00:00:00Z
date_updated: 2023-09-27T12:14:49Z
day: '01'
department:
- _id: UlWa
doi: 10.1016/j.comgeo.2017.06.016
external_id:
isi:
- '000412039700001'
intvolume: ' 66'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1602.01346
month: '12'
oa: 1
oa_version: Preprint
page: 1 - 13
publication: 'Computational Geometry: Theory and Applications'
publication_status: published
publisher: Elsevier
publist_id: '6860'
quality_controlled: '1'
related_material:
record:
- id: '1165'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: C-planarity of embedded cyclic c-graphs
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 66
year: '2017'
...
---
_id: '795'
abstract:
- lang: eng
text: 'We introduce a common generalization of the strong Hanani–Tutte theorem and
the weak Hanani–Tutte theorem: if a graph G has a drawing D in the plane where
every pair of independent edges crosses an even number of times, then G has a
planar drawing preserving the rotation of each vertex whose incident edges cross
each other evenly in D. The theorem is implicit in the proof of the strong Hanani–Tutte
theorem by Pelsmajer, Schaefer and Štefankovič. We give a new, somewhat simpler
proof.'
article_number: P3.18
article_processing_charge: No
article_type: original
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Jan
full_name: Kynčl, Jan
last_name: Kynčl
- first_name: Dömötör
full_name: Pálvölgyi, Dömötör
last_name: Pálvölgyi
citation:
ama: Fulek R, Kynčl J, Pálvölgyi D. Unified Hanani Tutte theorem. Electronic
Journal of Combinatorics. 2017;24(3). doi:10.37236/6663
apa: Fulek, R., Kynčl, J., & Pálvölgyi, D. (2017). Unified Hanani Tutte theorem.
Electronic Journal of Combinatorics. International Press. https://doi.org/10.37236/6663
chicago: Fulek, Radoslav, Jan Kynčl, and Dömötör Pálvölgyi. “Unified Hanani Tutte
Theorem.” Electronic Journal of Combinatorics. International Press, 2017.
https://doi.org/10.37236/6663.
ieee: R. Fulek, J. Kynčl, and D. Pálvölgyi, “Unified Hanani Tutte theorem,” Electronic
Journal of Combinatorics, vol. 24, no. 3. International Press, 2017.
ista: Fulek R, Kynčl J, Pálvölgyi D. 2017. Unified Hanani Tutte theorem. Electronic
Journal of Combinatorics. 24(3), P3.18.
mla: Fulek, Radoslav, et al. “Unified Hanani Tutte Theorem.” Electronic Journal
of Combinatorics, vol. 24, no. 3, P3.18, International Press, 2017, doi:10.37236/6663.
short: R. Fulek, J. Kynčl, D. Pálvölgyi, Electronic Journal of Combinatorics 24
(2017).
date_created: 2018-12-11T11:48:32Z
date_published: 2017-07-28T00:00:00Z
date_updated: 2022-03-18T12:58:53Z
day: '28'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.37236/6663
ec_funded: 1
file:
- access_level: open_access
checksum: ef320cff0f062051e858f929be6a3581
content_type: application/pdf
creator: dernst
date_created: 2019-01-18T14:04:08Z
date_updated: 2020-07-14T12:48:06Z
file_id: '5853'
file_name: 2017_ElectrCombi_Fulek.pdf
file_size: 236944
relation: main_file
file_date_updated: 2020-07-14T12:48:06Z
has_accepted_license: '1'
intvolume: ' 24'
issue: '3'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Electronic Journal of Combinatorics
publication_identifier:
issn:
- '10778926'
publication_status: published
publisher: International Press
publist_id: '6859'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Unified Hanani Tutte theorem
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '2017'
...
---
_id: '6517'
abstract:
- lang: eng
text: A (possibly degenerate) drawing of a graph G in the plane is approximable
by an embedding if it can be turned into an embedding by an arbitrarily small
perturbation. We show that testing, whether a drawing of a planar graph G in the
plane is approximable by an embedding, can be carried out in polynomial time,
if a desired embedding of G belongs to a fixed isotopy class, i.e., the rotation
system (or equivalently the faces) of the embedding of G and the choice of outer
face are fixed. In other words, we show that c-planarity with embedded pipes is
tractable for graphs with fixed embeddings. To the best of our knowledge an analogous
result was previously known essentially only when G is a cycle.
article_number: '34'
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
citation:
ama: 'Fulek R. Embedding graphs into embedded graphs. In: Vol 92. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ISAAC.2017.34'
apa: 'Fulek, R. (2017). Embedding graphs into embedded graphs (Vol. 92). Presented
at the ISAAC: International Symposium on Algorithms and Computation, Phuket, Thailand:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ISAAC.2017.34'
chicago: Fulek, Radoslav. “Embedding Graphs into Embedded Graphs,” Vol. 92. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ISAAC.2017.34.
ieee: 'R. Fulek, “Embedding graphs into embedded graphs,” presented at the ISAAC:
International Symposium on Algorithms and Computation, Phuket, Thailand, 2017,
vol. 92.'
ista: 'Fulek R. 2017. Embedding graphs into embedded graphs. ISAAC: International
Symposium on Algorithms and Computation vol. 92, 34.'
mla: Fulek, Radoslav. Embedding Graphs into Embedded Graphs. Vol. 92, 34,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ISAAC.2017.34.
short: R. Fulek, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
conference:
end_date: 2017-12-22
location: Phuket, Thailand
name: 'ISAAC: International Symposium on Algorithms and Computation'
start_date: 2017-12-09
date_created: 2019-06-04T12:11:52Z
date_published: 2017-12-01T00:00:00Z
date_updated: 2021-01-12T08:07:51Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPICS.ISAAC.2017.34
ec_funded: 1
file:
- access_level: open_access
checksum: fc7a643e29621c8bbe49d36b39081f31
content_type: application/pdf
creator: kschuh
date_created: 2019-06-04T12:20:35Z
date_updated: 2020-07-14T12:47:33Z
file_id: '6518'
file_name: 2017_LIPIcs-Fulek.pdf
file_size: 588982
relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: ' 92'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Embedding graphs into embedded graphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 92
year: '2017'
...
---
_id: '1164'
abstract:
- lang: eng
text: 'A drawing of a graph G is radial if the vertices of G are placed on concentric
circles C1, … , Ck with common center c, and edges are drawn radially: every edge
intersects every circle centered at c at most once. G is radial planar if it has
a radial embedding, that is, a crossing-free radial drawing. If the vertices of
G are ordered or partitioned into ordered levels (as they are for leveled graphs),
we require that the assignment of vertices to circles corresponds to the given
ordering or leveling. A pair of edges e and f in a graph is independent if e and
f do not share a vertex. We show that a graph G is radial planar if G has a radial
drawing in which every two independent edges cross an even number of times; the
radial embedding has the same leveling as the radial drawing. In other words,
we establish the strong Hanani-Tutte theorem for radial planarity. This characterization
yields a very simple algorithm for radial planarity testing.'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Michael
full_name: Pelsmajer, Michael
last_name: Pelsmajer
- first_name: Marcus
full_name: Schaefer, Marcus
last_name: Schaefer
citation:
ama: 'Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity II. In:
Vol 9801. Springer; 2016:468-481. doi:10.1007/978-3-319-50106-2_36'
apa: 'Fulek, R., Pelsmajer, M., & Schaefer, M. (2016). Hanani-Tutte for radial
planarity II (Vol. 9801, pp. 468–481). Presented at the GD: Graph Drawing and
Network Visualization, Athens, Greece: Springer. https://doi.org/10.1007/978-3-319-50106-2_36'
chicago: Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte
for Radial Planarity II,” 9801:468–81. Springer, 2016. https://doi.org/10.1007/978-3-319-50106-2_36.
ieee: 'R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity
II,” presented at the GD: Graph Drawing and Network Visualization, Athens, Greece,
2016, vol. 9801, pp. 468–481.'
ista: 'Fulek R, Pelsmajer M, Schaefer M. 2016. Hanani-Tutte for radial planarity
II. GD: Graph Drawing and Network Visualization, LNCS, vol. 9801, 468–481.'
mla: Fulek, Radoslav, et al. Hanani-Tutte for Radial Planarity II. Vol. 9801,
Springer, 2016, pp. 468–81, doi:10.1007/978-3-319-50106-2_36.
short: R. Fulek, M. Pelsmajer, M. Schaefer, in:, Springer, 2016, pp. 468–481.
conference:
end_date: 2016-09-21
location: Athens, Greece
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2016-09-19
date_created: 2018-12-11T11:50:29Z
date_published: 2016-12-08T00:00:00Z
date_updated: 2023-02-23T10:05:57Z
day: '08'
department:
- _id: UlWa
doi: 10.1007/978-3-319-50106-2_36
ec_funded: 1
external_id:
arxiv:
- '1608.08662'
intvolume: ' 9801'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1608.08662
month: '12'
oa: 1
oa_version: Preprint
page: 468 - 481
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: Springer
publist_id: '6193'
quality_controlled: '1'
related_material:
record:
- id: '1113'
relation: later_version
status: public
- id: '1595'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Hanani-Tutte for radial planarity II
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9801
year: '2016'
...
---
_id: '1165'
abstract:
- lang: eng
text: We show that c-planarity is solvable in quadratic time for flat clustered
graphs with three clusters if the combinatorial embedding of the underlying graph
is fixed. In simpler graph-theoretical terms our result can be viewed as follows.
Given a graph G with the vertex set partitioned into three parts embedded on a
2-sphere, our algorithm decides if we can augment G by adding edges without creating
an edge-crossing so that in the resulting spherical graph the vertices of each
part induce a connected sub-graph. We proceed by a reduction to the problem of
testing the existence of a perfect matching in planar bipartite graphs. We formulate
our result in a slightly more general setting of cyclic clustered graphs, i.e.,
the simple graph obtained by contracting each cluster, where we disregard loops
and multi-edges, is a cycle.
acknowledgement: "R. Fulek—The research leading to these results has received funding
from the People Programme (Marie Curie Actions) of the European Union’s Seventh
Framework Programme (FP7/2007-2013) under REA grant agreement no [291734].\r\nI
would like to thank Jan Kynčl and Dömötör Pálvölgyi for many comments and suggestions
that helped to improve the presentation of the result."
alternative_title:
- LNCS
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
citation:
ama: 'Fulek R. C-planarity of embedded cyclic c-graphs. In: Vol 9801. Springer;
2016:94-106. doi:10.1007/978-3-319-50106-2_8'
apa: 'Fulek, R. (2016). C-planarity of embedded cyclic c-graphs (Vol. 9801, pp.
94–106). Presented at the GD: Graph Drawing and Network Visualization, Athens,
Greece: Springer. https://doi.org/10.1007/978-3-319-50106-2_8'
chicago: Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs,” 9801:94–106.
Springer, 2016. https://doi.org/10.1007/978-3-319-50106-2_8.
ieee: 'R. Fulek, “C-planarity of embedded cyclic c-graphs,” presented at the GD:
Graph Drawing and Network Visualization, Athens, Greece, 2016, vol. 9801, pp.
94–106.'
ista: 'Fulek R. 2016. C-planarity of embedded cyclic c-graphs. GD: Graph Drawing
and Network Visualization, LNCS, vol. 9801, 94–106.'
mla: Fulek, Radoslav. C-Planarity of Embedded Cyclic c-Graphs. Vol. 9801,
Springer, 2016, pp. 94–106, doi:10.1007/978-3-319-50106-2_8.
short: R. Fulek, in:, Springer, 2016, pp. 94–106.
conference:
end_date: 2016-09-21
location: Athens, Greece
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2016-09-19
date_created: 2018-12-11T11:50:30Z
date_published: 2016-12-08T00:00:00Z
date_updated: 2023-09-27T12:14:48Z
day: '08'
department:
- _id: UlWa
doi: 10.1007/978-3-319-50106-2_8
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1602.01346
month: '12'
oa: 1
oa_version: Preprint
page: 94 - 106
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: Springer
publist_id: '6192'
quality_controlled: '1'
related_material:
record:
- id: '794'
relation: later_version
status: public
scopus_import: 1
status: public
title: C-planarity of embedded cyclic c-graphs
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: '9801 '
year: '2016'
...