الرسوم البيانية المسطحة الشاملة فرعية للأشجار

نظهر أنه يوجد رسم بياني خارجي مسطح يحتوي على O (n^c) من القمم حيث c = ₂ (3+10) 2. 623 ويحتوي على كل شجرة مكونة من n قمة كرسمة فرعية. وهذا يمدد نتيجة تشونغ وغراهام من عام 1983 الذين أظهروا أن هناك رسومات بيانية (غير مسطحة) مكونة من n قمة بها O (n n) حواف تحتوي على جميع الأشجار ذات n قمة كرسوم فرعية ونتيجة جولدبيرغ وليفشيتس من 1968 الذين أظهروا أنه يوجد شجرة شاملة للأشجار ذات n قمة على n^O ( (n) ) من القمم. علاوة على ذلك، نحدد عدد القمم المطلوبة في أسوأ الحالات لرسم بياني مسطح لاحتواء ثلاث أشجار معينة كرسوم فرعية لتكون من رتبة 32n، حتى لو كانت الأشجار الثلاثة ديدان. هذا يجيب على سؤال طرح مؤخرًا بواسطة أليكيو وآخرين في عام 2024. أخيرًا، نحقق في الرسوم البيانية (الخارجية) المسطحة التي تحتوي على جميع الرسوم البيانية (الخارجية) المسطحة كرسوم فرعية، مع تحديد حدود دنيا أسية في كلتا الحالتين. كما نقوم بإنشاء رسم بياني مسطح على n^O ( (n) ) من القمم تحتوي على جميع الرسوم البيانية الخارجية المكونة من n قمة كرسوم فرعية.