---
_id: '10335'
abstract:
- lang: eng
  text: "Van der Holst and Pendavingh introduced a graph parameter σ, which coincides
    with the more famous Colin de Verdière graph parameter μ for small values. However,
    the definition of a is much more geometric/topological directly reflecting embeddability
    properties of the graph. They proved μ(G) ≤ σ(G) + 2 and conjectured σ(G) ≤ σ(G)
    for any graph G. We confirm this conjecture. As far as we know, this is the first
    topological upper bound on σ(G) which is, in general, tight.\r\nEquality between
    μ and σ does not hold in general as van der Holst and Pendavingh showed that there
    is a graph G with μ(G) ≤ 18 and σ(G) ≥ 20. We show that the gap appears at much
    smaller values, namely, we exhibit a graph H for which μ(H) ≥ 7 and σ(H) ≥ 8.
    We also prove that, in general, the gap can be large: The incidence graphs Hq
    of finite projective planes of order q satisfy μ(Hq) ∈ O(q3/2) and σ(Hq) ≥ q2."
acknowledgement: 'V. K. gratefully acknowledges the support of Austrian Science Fund
  (FWF): P 30902-N35. This work was done mostly while he was employed at the University
  of Innsbruck. During the early stage of this research, V. K. was partially supported
  by Charles University project GAUK 926416. M. T. is supported by the grant no. 19-04113Y
  of the Czech Science Foundation(GA ˇCR) and partially supported by Charles University
  project UNCE/SCI/004.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Vojtech
  full_name: Kaluza, Vojtech
  id: 21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E
  last_name: Kaluza
  orcid: 0000-0002-2512-8698
- first_name: Martin
  full_name: Tancer, Martin
  id: 38AC689C-F248-11E8-B48F-1D18A9856A87
  last_name: Tancer
  orcid: 0000-0002-1191-6714
citation:
  ama: Kaluza V, Tancer M. Even maps, the Colin de Verdière number and representations
    of graphs. <i>Combinatorica</i>. 2022;42:1317-1345. doi:<a href="https://doi.org/10.1007/s00493-021-4443-7">10.1007/s00493-021-4443-7</a>
  apa: Kaluza, V., &#38; Tancer, M. (2022). Even maps, the Colin de Verdière number
    and representations of graphs. <i>Combinatorica</i>. Springer Nature. <a href="https://doi.org/10.1007/s00493-021-4443-7">https://doi.org/10.1007/s00493-021-4443-7</a>
  chicago: Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number
    and Representations of Graphs.” <i>Combinatorica</i>. Springer Nature, 2022. <a
    href="https://doi.org/10.1007/s00493-021-4443-7">https://doi.org/10.1007/s00493-021-4443-7</a>.
  ieee: V. Kaluza and M. Tancer, “Even maps, the Colin de Verdière number and representations
    of graphs,” <i>Combinatorica</i>, vol. 42. Springer Nature, pp. 1317–1345, 2022.
  ista: Kaluza V, Tancer M. 2022. Even maps, the Colin de Verdière number and representations
    of graphs. Combinatorica. 42, 1317–1345.
  mla: Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number
    and Representations of Graphs.” <i>Combinatorica</i>, vol. 42, Springer Nature,
    2022, pp. 1317–45, doi:<a href="https://doi.org/10.1007/s00493-021-4443-7">10.1007/s00493-021-4443-7</a>.
  short: V. Kaluza, M. Tancer, Combinatorica 42 (2022) 1317–1345.
date_created: 2021-11-25T13:49:16Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2023-08-02T06:43:27Z
day: '01'
ddc:
- '514'
- '516'
department:
- _id: UlWa
doi: 10.1007/s00493-021-4443-7
external_id:
  arxiv:
  - '1907.05055'
  isi:
  - '000798210100003'
intvolume: '        42'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: ' https://doi.org/10.48550/arXiv.1907.05055'
month: '12'
oa: 1
oa_version: Preprint
page: 1317-1345
publication: Combinatorica
publication_identifier:
  issn:
  - 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Even maps, the Colin de Verdière number and representations of graphs
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 42
year: '2022'
...
---
_id: '9582'
abstract:
- lang: eng
  text: The problem of finding dense induced bipartite subgraphs in H-free graphs
    has a long history, and was posed 30 years ago by Erdős, Faudree, Pach and Spencer.
    In this paper, we obtain several results in this direction. First we prove that
    any H-free graph with minimum degree at least d contains an induced bipartite
    subgraph of minimum degree at least cH log d/log log d, thus nearly confirming
    one and proving another conjecture of Esperet, Kang and Thomassé. Complementing
    this result, we further obtain optimal bounds for this problem in the case of
    dense triangle-free graphs, and we also answer a question of Erdœs, Janson, Łuczak
    and Spencer.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Matthew Alan
  full_name: Kwan, Matthew Alan
  id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
  last_name: Kwan
  orcid: 0000-0002-4003-7567
- first_name: Shoham
  full_name: Letzter, Shoham
  last_name: Letzter
- first_name: Benny
  full_name: Sudakov, Benny
  last_name: Sudakov
- first_name: Tuan
  full_name: Tran, Tuan
  last_name: Tran
citation:
  ama: Kwan MA, Letzter S, Sudakov B, Tran T. Dense induced bipartite subgraphs in
    triangle-free graphs. <i>Combinatorica</i>. 2020;40(2):283-305. doi:<a href="https://doi.org/10.1007/s00493-019-4086-0">10.1007/s00493-019-4086-0</a>
  apa: Kwan, M. A., Letzter, S., Sudakov, B., &#38; Tran, T. (2020). Dense induced
    bipartite subgraphs in triangle-free graphs. <i>Combinatorica</i>. Springer. <a
    href="https://doi.org/10.1007/s00493-019-4086-0">https://doi.org/10.1007/s00493-019-4086-0</a>
  chicago: Kwan, Matthew Alan, Shoham Letzter, Benny Sudakov, and Tuan Tran. “Dense
    Induced Bipartite Subgraphs in Triangle-Free Graphs.” <i>Combinatorica</i>. Springer,
    2020. <a href="https://doi.org/10.1007/s00493-019-4086-0">https://doi.org/10.1007/s00493-019-4086-0</a>.
  ieee: M. A. Kwan, S. Letzter, B. Sudakov, and T. Tran, “Dense induced bipartite
    subgraphs in triangle-free graphs,” <i>Combinatorica</i>, vol. 40, no. 2. Springer,
    pp. 283–305, 2020.
  ista: Kwan MA, Letzter S, Sudakov B, Tran T. 2020. Dense induced bipartite subgraphs
    in triangle-free graphs. Combinatorica. 40(2), 283–305.
  mla: Kwan, Matthew Alan, et al. “Dense Induced Bipartite Subgraphs in Triangle-Free
    Graphs.” <i>Combinatorica</i>, vol. 40, no. 2, Springer, 2020, pp. 283–305, doi:<a
    href="https://doi.org/10.1007/s00493-019-4086-0">10.1007/s00493-019-4086-0</a>.
  short: M.A. Kwan, S. Letzter, B. Sudakov, T. Tran, Combinatorica 40 (2020) 283–305.
date_created: 2021-06-22T06:42:26Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2023-02-23T14:01:45Z
day: '01'
doi: 10.1007/s00493-019-4086-0
extern: '1'
external_id:
  arxiv:
  - '1810.12144'
intvolume: '        40'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1810.12144
month: '04'
oa: 1
oa_version: Preprint
page: 283-305
publication: Combinatorica
publication_identifier:
  eissn:
  - 1439-6912
  issn:
  - 0209-9683
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dense induced bipartite subgraphs in triangle-free graphs
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 40
year: '2020'
...
---
_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. <i>Combinatorica</i>. 2019;39(6):1267-1279. doi:<a
    href="https://doi.org/10.1007/s00493-019-3905-7">10.1007/s00493-019-3905-7</a>
  apa: Fulek, R., &#38; Kynčl, J. (2019). Counterexample to an extension of the Hanani-Tutte
    theorem on the surface of genus 4. <i>Combinatorica</i>. Springer Nature. <a href="https://doi.org/10.1007/s00493-019-3905-7">https://doi.org/10.1007/s00493-019-3905-7</a>
  chicago: Fulek, Radoslav, and Jan Kynčl. “Counterexample to an Extension of the
    Hanani-Tutte Theorem on the Surface of Genus 4.” <i>Combinatorica</i>. Springer
    Nature, 2019. <a href="https://doi.org/10.1007/s00493-019-3905-7">https://doi.org/10.1007/s00493-019-3905-7</a>.
  ieee: R. Fulek and J. Kynčl, “Counterexample to an extension of the Hanani-Tutte
    theorem on the surface of genus 4,” <i>Combinatorica</i>, 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.” <i>Combinatorica</i>, vol. 39, no. 6, Springer
    Nature, 2019, pp. 1267–79, doi:<a href="https://doi.org/10.1007/s00493-019-3905-7">10.1007/s00493-019-3905-7</a>.
  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: '4053'
abstract:
- lang: eng
  text: We show that the maximum number of edges bounding m faces in an arrangement
    of n line segments in the plane is O(m2/3n2/3+nα(n)+nlog m). This improves a previous
    upper bound of Edelsbrunner et al. [5] and almost matches the best known lower
    bound which is Ω(m2/3n2/3+nα(n)). In addition, we show that the number of edges
    bounding any m faces in an arrangement of n line segments with a total of t intersecting
    pairs is O(m2/3t1/3+nα(t/n)+nmin{log m,log t/n}), almost matching the lower bound
    of Ω(m2/3t1/3+nα(t/n)) demonstrated in this paper.
article_processing_charge: No
article_type: original
author:
- first_name: Boris
  full_name: Aronov, Boris
  last_name: Aronov
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: Aronov B, Edelsbrunner H, Guibas L, Sharir M. The number of edges of many faces
    in a line segment arrangement. <i>Combinatorica</i>. 1992;12(3):261-274. doi:<a
    href="https://doi.org/10.1007/BF01285815">10.1007/BF01285815</a>
  apa: Aronov, B., Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1992). The number
    of edges of many faces in a line segment arrangement. <i>Combinatorica</i>. Springer.
    <a href="https://doi.org/10.1007/BF01285815">https://doi.org/10.1007/BF01285815</a>
  chicago: Aronov, Boris, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir.
    “The Number of Edges of Many Faces in a Line Segment Arrangement.” <i>Combinatorica</i>.
    Springer, 1992. <a href="https://doi.org/10.1007/BF01285815">https://doi.org/10.1007/BF01285815</a>.
  ieee: B. Aronov, H. Edelsbrunner, L. Guibas, and M. Sharir, “The number of edges
    of many faces in a line segment arrangement,” <i>Combinatorica</i>, vol. 12, no.
    3. Springer, pp. 261–274, 1992.
  ista: Aronov B, Edelsbrunner H, Guibas L, Sharir M. 1992. The number of edges of
    many faces in a line segment arrangement. Combinatorica. 12(3), 261–274.
  mla: Aronov, Boris, et al. “The Number of Edges of Many Faces in a Line Segment
    Arrangement.” <i>Combinatorica</i>, vol. 12, no. 3, Springer, 1992, pp. 261–74,
    doi:<a href="https://doi.org/10.1007/BF01285815">10.1007/BF01285815</a>.
  short: B. Aronov, H. Edelsbrunner, L. Guibas, M. Sharir, Combinatorica 12 (1992)
    261–274.
date_created: 2018-12-11T12:06:40Z
date_published: 1992-09-01T00:00:00Z
date_updated: 2022-03-15T15:44:26Z
day: '01'
doi: 10.1007/BF01285815
extern: '1'
intvolume: '        12'
issue: '3'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF01285815
month: '09'
oa_version: None
page: 261 - 274
publication: Combinatorica
publication_identifier:
  issn:
  - 0209-9683
publication_status: published
publisher: Springer
publist_id: '2074'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The number of edges of many faces in a line segment arrangement
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 12
year: '1992'
...
---
_id: '4069'
abstract:
- lang: eng
  text: Let C be a cell complex in d-dimensional Euclidean space whose faces are obtained
    by orthogonal projection of the faces of a convex polytope in d + 1 dimensions.
    For example, the Delaunay triangulation of a finite point set is such a cell complex.
    This paper shows that the in front/behind relation defined for the faces of C
    with respect to any fixed viewpoint x is acyclic. This result has applications
    to hidden line/surface removal and other problems in computational geometry.
acknowledgement: Research reported in this paper was supported by the National Science
  Foundation under grant CCR-8714565.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
citation:
  ama: Edelsbrunner H. An acyclicity theorem for cell complexes in d dimension. <i>Combinatorica</i>.
    1990;10(3):251-260. doi:<a href="https://doi.org/10.1007/BF02122779">10.1007/BF02122779</a>
  apa: Edelsbrunner, H. (1990). An acyclicity theorem for cell complexes in d dimension.
    <i>Combinatorica</i>. Springer. <a href="https://doi.org/10.1007/BF02122779">https://doi.org/10.1007/BF02122779</a>
  chicago: Edelsbrunner, Herbert. “An Acyclicity Theorem for Cell Complexes in d Dimension.”
    <i>Combinatorica</i>. Springer, 1990. <a href="https://doi.org/10.1007/BF02122779">https://doi.org/10.1007/BF02122779</a>.
  ieee: H. Edelsbrunner, “An acyclicity theorem for cell complexes in d dimension,”
    <i>Combinatorica</i>, vol. 10, no. 3. Springer, pp. 251–260, 1990.
  ista: Edelsbrunner H. 1990. An acyclicity theorem for cell complexes in d dimension.
    Combinatorica. 10(3), 251–260.
  mla: Edelsbrunner, Herbert. “An Acyclicity Theorem for Cell Complexes in d Dimension.”
    <i>Combinatorica</i>, vol. 10, no. 3, Springer, 1990, pp. 251–60, doi:<a href="https://doi.org/10.1007/BF02122779">10.1007/BF02122779</a>.
  short: H. Edelsbrunner, Combinatorica 10 (1990) 251–260.
date_created: 2018-12-11T12:06:45Z
date_published: 1990-09-01T00:00:00Z
date_updated: 2022-02-21T11:08:30Z
day: '01'
doi: 10.1007/BF02122779
extern: '1'
intvolume: '        10'
issue: '3'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02122779
month: '09'
oa_version: None
page: 251 - 260
publication: Combinatorica
publication_identifier:
  eissn:
  - 1439-6912
  issn:
  - 0209-9683
publication_status: published
publisher: Springer
publist_id: '2050'
quality_controlled: '1'
scopus_import: '1'
status: public
title: An acyclicity theorem for cell complexes in d dimension
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 10
year: '1990'
...