Den geometriska tjockleken på en graf är det minsta antalet lager så att grafen kan ritas i planet med kanter som raka segment, och med varje kant tilldelad ett lager så att inga två kanter i samma lager kors. Vi anser en variation på detta tema där varje kant tillåts en böj. Vi bevisar att hörnen i en n-vertex m-kant graf kan placeras i en ε n × ε n rutnät och kanterna tilldelas O ( ε m) lager, så att varje kant ritas med högst en böj och inga två kanter på samma lager kors. Beviset är en tvådimensionell generalisering av en sats av Malitz (J. Algorithms 17.1 (1994) 71-84) om bokinbäddningar. Vi får en Las Vegas algoritm för att beräkna ritningen i O(m log 3 n logg n) tid (med hög sannolikhet).
I REF Wood visar att hörnen i en n-vertex m-kantkurva kan placeras i ett rutnät som är lika med n-vertex m-kant, så att varje kant ritas med högst en böj och inga två kanter på samma lagerkors.
Geometric Thickness in a Grid
{'venue': 'Discrete Mathematics', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}