On the achievable average degrees in 2-crossing-critical graphs

HLINĚNÝ, Petr and Michal KORBELA. On the achievable average degrees in 2-crossing-critical graphs. Acta Math. Univ. Comenianae. 2019, vol. 88, No 3, p. 787-793. ISSN 0231-6986.

Basic information

• Original name: On the achievable average degrees in 2-crossing-critical graphs
• Authors: HLINĚNÝ, Petr (203 Czech Republic, guarantor, belonging to the institution) and Michal KORBELA (703 Slovakia, belonging to the institution).
• Edition: Acta Math. Univ. Comenianae, 2019, 0231-6986.

Other information

• Original language: English
• Type of outcome: Article in a journal
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: Slovakia
• Confidentiality degree: is not subject to a state or trade secret
• WWW: URL
• RIV identification code: RIV/00216224:14330/19:00112160
• Organization unit: Faculty of Informatics
• UT WoS: 000484349000067
• Keywords in English: graph; crossing number; crossing-critical
• Tags: formela-conference

Abstract

c-Crossing-critical graphs are the minimal graphs requiring at least c edge crossings in every drawing in the plane. The structure of these obstructions is very rich for every c>=2. Although, at least in the first nontrivial case of c=2, their structure is well understood. For example, we know that, aside of finitely many small exceptions, the 2-crossing-critical graphs have vertex degrees from the set {3, 4, 5, 6} and their average degree can achieve exactly all rational values from the interval [3+1/2 , 4+2/3]. Continuing in depth in this research direction, we determine which average degrees of 2-crossing-critical graphs are possible if we restrict their vertex degrees to proper subsets of {3, 4, 5, 6}. In particular, we identify the (surprising) subcases in which, by number-theoretical reasons, the achievable average degrees form discontinuous sets of rationals.

Links

• MUNI/A/1018/2018, interní kód MU: Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VIII.

Investor: Masaryk University, Category A