Descomposición en orejas
El siguiente resultado se debe a Hassler Whitney (1932): El siguiente resultado se debe a Herbert Robbins (1939): En ambos casos el número de orejas es necesariamente igual al rango de circuito del grafo dado.
Robbins introdujo la descomposición en orejas de grafos conectados por 2 aristas como una herramienta para probar el teorema de Robbins, que estos son exactamente los grafos a los que se les puede dar una orientación fuertemente conexa.
Debido al trabajo pionero de Whitney y Robbins sobre las descomposiciones en orejas, a veces también se denominan "síntesis de Whitney-Robbins" (Gross y Yellen, 2006).
Este resultado fue declarado explícitamente por primera vez por Cheriyan y Maheshwari (1988), pero como lo describe Schmidt (2013b), es equivalente a un resultado incluido en la tesis doctoral de Lee Mondshein publicada en 1971.
Las estructuras estrechamente relacionadas con las descomposiciones en orejas sin separación de grafos planos máximos, llamadas ordenaciones canónicas, también son una herramienta estándar en el dibujo de grafos.
Entonces, se verifica el siguiente teorema (Bang-Jensen y Gutin, 2007, Theorem 7.2.2): Una descomposición en orejas es impar si cada una de sus orejas incluye un número impar de aristas.
El siguiente resultado se debe a David Eppstein (1992): Además, cualquier descomposición en orejas abiertas de un grafo en serie-paralelo conectado por 2 vértices debe estar anidada.
Usando esta definición, un matroide puede definirse como factor crítico cuando tiene una descomposición en orejas en la que cada circuito en la secuencia tiene un número impar de elementos nuevos (Szegedy y Szegedy, 2006).
En Schmidt (2013a) se proporciona un enfoque voraz simple que calcula al mismo tiempo las descomposiciones en orejas, las descomposiciones en orejas abiertas, las numeraciones y las orientaciones en tiempo lineal (si existen).
El enfoque se basa en el cálculo de una descomposición en orejas especial denominada descomposición en cadena mediante una regla de generación de rutas.Schmidt (2013b) muestra que las descomposiciones en orejas sin separación también pueden construirse en tiempo lineal.Lovász (1985),Maon, Schieber y Vishkin (1986) y Miller y Ramachandran (1986) proporcionaron algoritmos en paralelo eficientes para obtener descomposiciones en orejas de varios tipos.
Una descomposición en orejas de un matroide dado, con la restricción adicional de que cada oreja contiene el mismo elemento fijo del matroide, se puede encontrar en tiempo polinómico con acceso a un oráculo de independencia para el matroide (Coullard y Hellerstein, 1996).
