---
_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: '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: '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
license: https://creativecommons.org/licenses/by/4.0/
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: '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: '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: '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'
...